// OpentTxl-C Version 11 rule compiler
// J.R. Cordy, Jan 2023

// Copyright 2023, James R. Cordy and others

// Permission is hereby granted, free of charge, to any person obtaining a copy of this software 
// and associated documentation files (the “Software”), to deal in the Software without restriction, 
// including without limitation the rights to use, copy, modify, merge, publish, distribute, sublicense, 
// and/or sell copies of the Software, and to permit persons to whom the Software is furnished to do so, 
// subject to the following conditions:

// The above copyright notice and this permission notice shall be included in all copies 
// or substantial portions of the Software.

// THE SOFTWARE IS PROVIDED “AS IS”, WITHOUT WARRANTY OF ANY KIND, EXPRESS OR IMPLIED, 
// INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE 
// AND NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, 
// DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, 
// OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.

// The TXL rule compiler.
// Compiles the rule and functions in the TXL program into a rule table which encodes the pattern
// and replacement parse trees to be matched or instantiated when the rules are run.
// Takes as input the parsed TXL program as a parse tree according to the TXL bootstrap grammar
// and processes the contents of each parsed rule and function statement. 

// Modification Log

// v11.0 Initial revision, adapted from OpenTxl 11.0

// v11.1 Added anonymous conditions, e.g., where _ [test]
//       Fixed local variable binding bug

// v11.3 Added multiple skip criteria, e.g., skipping [x] [y] replace [z] ...

#define COMPILER

// I/O, strings, memory allocation
#include "support.h"

// Global modules
#include "limits.h"
#include "options.h"
#include "tokens.h"
#include "trees.h"
#include "shared.h"
#include "idents.h"
#include "symbols.h"
#include "errors.h"
#include "txltree.h"

// Dependencies on other phases
#include "scan.h"
#include "rules.h"
#include "parse.h"
#include "unparse.h"

// Check interface consistency
#include "comprul.h"

// Current compiling context
static string ruleCompiler_context;         // ""
static int ruleCompiler_currentRuleIndex;   // 0

// Is this program polymorphic?
static bool ruleCompiler_polymorphicProgram;  // false


static void ruleCompiler_processRuleCall (const tokenT scopetype, const treePT ruleCallTP, struct ruleLocalsT *varsSoFar, 
        treePT *parsedCallTP, const bool isConditionCall)
{
    bool isCondition = isConditionCall;

    // Enter the called rule in the rule table if not yet defined
    const tokenT ruleName = txltree_ruleCall_nameT (ruleCallTP);
    int ruleIndex = rule_enterRule (ruleName);

    // Remember that we called this rule
    rule_enterRuleCall (ruleCompiler_context, ruleCompiler_currentRuleIndex, ruleIndex);

    // For rule calls, the name field represents the called rule's rule index
    *parsedCallTP = tree_newTreeInit (treeKind_ruleCall, ruleIndex, ruleIndex, 0, nilKid);

    // We process query rule calls [?R] as calls to [R]
    // The relation betweeh them is resolved later, when we discover [?R] is undefined
    if (stringchar (*ident_idents[ruleName], 1) == '?') {
        rule_setCalled (ruleIndex, true);
        rule_setTarget (ruleIndex, scopetype);
        rule_setIsCondition (ruleIndex, true);
        string realRuleNameString;
        substring (realRuleNameString, *ident_idents[ruleName], 2, stringlen (*ident_idents[ruleName]));
        const tokenT realRuleName = ident_install (realRuleNameString, treeKind_id);
        ruleIndex = rule_enterRule (realRuleName);
        // Remember that we called the target rule
        rule_enterRuleCall (ruleCompiler_context, ruleCompiler_currentRuleIndex, ruleIndex);
        // And that it is not itself a condition rule
        isCondition = false;
    }

    bool eaching = false;

    struct ruleT *r = &(rule_rules[ruleIndex]);

    if ((r->called) || (r->defined)) {
        // already defined or a successive call - must check scope and parameter type consistency

        if (((scopetype != r->target) && (r->target != any_T)) && (scopetype != any_T)) {
            if (r->defined) {
                if ((r->kind == ruleKind_function) && (!(r->starred))) {
                    string message;
                    stringprintf (message, "Scope of function '%s' is not of target type", *ident_idents[r->name]);
                    error (ruleCompiler_context, message, WARNING, 301);
                }
            } else {
                // previously called with a different scope type
                rule_setTarget (ruleIndex, any_T);
            }
        }

        if (isCondition) {
            if ((r->defined) && (!(r->isCondition))) {
                string message;
                stringprintf (message, "'replace' rule '%s' used as a 'where' condition", *ident_idents[r->name]);
                error (ruleCompiler_context, message, FATAL, 302);
            }
            rule_setIsCondition (ruleIndex, true);
        }

        // actuals parse like literals, even when they are not!
        treePT literalsTP = txltree_ruleCall_literalsTP (ruleCallTP);

        // types of eached parameters, if any
        tokenT p1type = any_T;
        tokenT p2type = any_T;

        if (tree_plural_emptyP (literalsTP)) {
            if (r->localVars.nformals != 0) {
                string message;
                stringprintf (message, "Number of parameters to rule/function '%s' differs from definition or previous call", 
                    *ident_idents[r->name]);
                error (ruleCompiler_context, message, FATAL, 303);
            }

            // if it is a (polymorphic) predefined function, check the type of the scope now, to save checking at run time
            if (r->kind == ruleKind_predefined) {
                rule_checkPredefinedFunctionScopeAndParameters (ruleCompiler_context, ruleIndex, scopetype, empty_T, empty_T);
            }

        } else {
            const kidPT newKid = tree_newKid ();
            tree_setKids (*parsedCallTP, newKid);
            kidPT parsedActualsKP = tree_trees[*parsedCallTP].kidsKP;

            for (int actualCount = 1; actualCount <= r->localVars.nformals; actualCount++) {
                tokenT actualName = txltree_literal_tokenT (tree_plural_firstTP (literalsTP));
                tokenT actualRawName = txltree_literal_rawtokenT (tree_plural_firstTP (literalsTP));

                // It might be an 'each' indicator
                if (actualName == each_T) {
                    literalsTP = tree_plural_restTP (literalsTP);

                    if (eaching || tree_plural_emptyP (literalsTP)) {
                        string message;
                        stringprintf (message, "Rule/function '%s' used with empty or double 'each'", *ident_idents[r->name]);
                        error (ruleCompiler_context, message, FATAL, 304);
                    }

                    eaching = true;
                    actualName = txltree_literal_tokenT (tree_plural_firstTP (literalsTP));
                    actualRawName = txltree_literal_rawtokenT (tree_plural_firstTP (literalsTP));
                }

                const treePT newTP = tree_newTreeInit (treeKind_empty, actualName, actualRawName, 0, nilKid);
                tree_setKidTree (parsedActualsKP, newTP);

                // We know the name, but is it a literal or a TXL variable?
                int localIndex = NOT_FOUND;
                if (!txltree_isQuotedLiteral (tree_plural_firstTP (literalsTP))) {
                    for (int i = 1; i <= varsSoFar->nlocals; i++) {
                        if (rule_ruleLocals[varsSoFar->localsBase + i].name == actualName) {
                            localIndex = i;
                            break;
                        }
                    }
                }

                if (localIndex != NOT_FOUND) {
                    // it's a variable
                    rule_incLocalRefs (varsSoFar->localsBase + localIndex, 1);

                    // keep track of the last reference if in a replacement
                    rule_setLocalLastRef (varsSoFar->localsBase + localIndex, tree_kids[parsedActualsKP]);
                    tree_setKind (tree_kids[parsedActualsKP], treeKind_subsequentUse);
                    tree_setCount ((tree_kids[parsedActualsKP]), localIndex);

                    // figure out the effective type
                    tokenT effectiveType = rule_ruleLocals[varsSoFar->localsBase + localIndex].typename_;
                    if (eaching) {
                        // we're in the scope of an 'each' - we indicate that with non-null kidsKP
                        tree_setKids (tree_kids[parsedActualsKP], maxKids);
                        if (tree_isListOrRepeatType (effectiveType)) {
                            effectiveType = tree_listOrRepeatBaseType (effectiveType);
                        } else {
                            string message;
                            stringprintf (message, "'each' argument of rule/function '%s' is not a list or repeat", *ident_idents[r->name]);
                            error (ruleCompiler_context, message, FATAL, 305);
                        }
                    } else {
                        // make sure we mark it as NOT an each!
                        tree_setKids (tree_kids[parsedActualsKP], nilKid);
                    }

                    const tokenT formalType = rule_ruleLocals[r->localVars.localsBase + actualCount].typename_;

                    if ((formalType != effectiveType) && (formalType != any_T)) {
                        string message;
                        stringprintf (message, "Type of actual parameter '%s' of rule/function '%s' does not agree with definition or previous call",
                            *ident_idents[rule_ruleLocals[varsSoFar->localsBase + localIndex].name],
                            *ident_idents[r->name]);
                        error (ruleCompiler_context, message, FATAL, 306);
                    }

                    if (actualCount == 1) {
                        p1type = effectiveType;
                    } else {
                        if (actualCount == 2) {
                            p2type = effectiveType;
                        }
                    }

                } else {
                    // it's a literal
                    const enum treeKindT literalKind = txltree_literal_kindT (tree_plural_firstTP (literalsTP));

                    if ((literalKind == treeKind_id) && (!txltree_isQuotedLiteral (tree_plural_firstTP (literalsTP)))) {
                        string message;
                        stringprintf (message, "Literal actual parameter '%s' of rule/function '%s' is not quoted", 
                            *ident_idents[actualRawName],
                            *ident_idents[r->name]);
                        error (ruleCompiler_context, message, WARNING, 307);
                    }

                    tree_setKind (tree_kids[parsedActualsKP], literalKind);

                    const tokenT literalType = tree_literalTypeName (tree_trees[tree_kids[parsedActualsKP]].kind);

                    if (eaching) {
                        // we're in the scope of an 'each' - so a literal can't be right!
                        string message;
                        stringprintf (message, "'each' argument of rule/function '%s' is not a list or repeat", *ident_idents[r->name]);
                        error (ruleCompiler_context, message, FATAL, 305);
                    }

                    const tokenT formalType = rule_ruleLocals[r->localVars.localsBase + actualCount].typename_;

                    if ((literalType != formalType) && (formalType != any_T)) {
                        string message;
                        stringprintf (message, "Type of actual parameter '%s' of rule/function '%s' does not agree with definition or previous call",
                            *ident_idents[actualName],
                            *ident_idents[r->name]);
                        error (ruleCompiler_context, message, FATAL, 306);
                    }

                    if (actualCount == 1) {
                        p1type = literalType;
                    } else {
                        if (actualCount == 2) {
                            p2type = literalType;
                        }
                    }
                }

                literalsTP = tree_plural_restTP (literalsTP);

                if (tree_plural_emptyP (literalsTP)) {
                    if (actualCount < r->localVars.nformals) {
                        string message;
                        stringprintf (message, "Number of parameters passed to rule/function '%s' differs from definition or previous call", 
                            *ident_idents[r->name]); 
                        error (ruleCompiler_context, message, FATAL, 309);
                    }
                    break;
                }

                parsedActualsKP = tree_newKid ();
            }

            // mark end of actuals with nilTree
            parsedActualsKP = tree_newKid ();
            tree_setKidTree (parsedActualsKP, nilTree);

            if (!tree_plural_emptyP (literalsTP)) {
                string message;
                stringprintf (message, "Number of parameters passed to rule/function '%s' differs from definition or previous call", 
                        *ident_idents[r->name]);
                error (ruleCompiler_context, message, FATAL, 309);
            }

            // if it is a (polymorphic) predefined function, check the types of scope 
            // and parameters now to save doing it at run time
            if (r->kind == ruleKind_predefined) {
                rule_checkPredefinedFunctionScopeAndParameters (ruleCompiler_context, ruleIndex, scopetype, p1type, p2type);
            }
        }

    } else {
        // first call - must enter parameter types and count
        rule_setCalled (ruleIndex, true);
        rule_setTarget (ruleIndex, scopetype);
        rule_setIsCondition (ruleIndex, isCondition);
        rule_setLocalsBase (ruleIndex, rule_ruleFormalCount);    // special temporary space in ruleLocals for formal info

        if (rule_ruleFormalCount + maxParameters > maxTotalRuleParameters) {
            string message;
            stringprintf (message, "Too many total parameters of rules in TXL program (> %d)", maxTotalRuleParameters);
            error (ruleCompiler_context, message, LIMIT_FATAL, 336);
        }

        // actuals parse like literals, even when they are not!
        treePT literalsTP = txltree_ruleCall_literalsTP (ruleCallTP);
        int actualCount = 0;

        if (!tree_plural_emptyP (literalsTP)) {
            const kidPT newKid = tree_newKid ();
            tree_setKids (*parsedCallTP, newKid);
            treePT parsedActualsKP = tree_trees[*parsedCallTP].kidsKP;
            while (true) {
                if (actualCount == maxParameters) {
                    string message;
                    stringprintf (message, "Too many rule/function parameters, rule/function '%s' (> %d)", 
                        *ident_idents[r->name], maxParameters);
                    error (ruleCompiler_context, message, LIMIT_FATAL, 311);
                }

                actualCount += 1;

                tokenT actualName = txltree_literal_tokenT (tree_plural_firstTP (literalsTP));
                tokenT actualRawName = txltree_literal_rawtokenT (tree_plural_firstTP (literalsTP));

                // It might be an 'each' indicator
                if (actualName == each_T) {
                    literalsTP = tree_plural_restTP (literalsTP);

                    if (eaching || tree_plural_emptyP (literalsTP)) {
                        string message;
                        stringprintf (message, "Rule/function '%s' used with empty or double 'each'", *ident_idents[r->name]);
                        error (ruleCompiler_context, message, FATAL, 312);
                    }

                    eaching = true;
                    actualName = txltree_literal_tokenT (tree_plural_firstTP (literalsTP));
                    actualRawName = txltree_literal_rawtokenT (tree_plural_firstTP (literalsTP));
                }

                const treePT newTP = tree_newTreeInit (treeKind_empty, actualName, actualRawName, 0, nilKid);
                tree_setKidTree (parsedActualsKP, newTP);

                // We know the name, but is it a literal or a TXL variable?
                int localIndex = NOT_FOUND;
                if (!txltree_isQuotedLiteral (tree_plural_firstTP (literalsTP))) {
                    for (int i = 1; i <= varsSoFar->nlocals; i++) {
                        if (rule_ruleLocals[varsSoFar->localsBase + i].name == actualName) {
                            localIndex = i;
                            break;
                        }
                    }
                }

                if (localIndex != NOT_FOUND) {
                    // it's a variable
                    rule_incLocalRefs (varsSoFar->localsBase + localIndex, 1);

                    // keep track of the last reference if in a replacement
                    rule_setLocalLastRef (varsSoFar->localsBase + localIndex, tree_kids[parsedActualsKP]);
                    tree_setKind (tree_kids[parsedActualsKP], treeKind_subsequentUse);
                    tree_setCount (tree_kids[parsedActualsKP], localIndex);  // save looking for it later

                    // figure out the effective type
                    tokenT effectiveType = rule_ruleLocals[varsSoFar->localsBase + localIndex].typename_;
                    if (eaching) {
                        // we're in the scope of an 'each' - indicate with a non-null kidsKP
                        tree_setKids (tree_kids[parsedActualsKP], maxKids);
                        if (tree_isListOrRepeatType (effectiveType)) {
                            effectiveType = tree_listOrRepeatBaseType (effectiveType);
                        } else {
                            string message;
                            stringprintf (message, "'each' argument of rule/function '%s' is not a list or repeat", 
                                *ident_idents[r->name]);
                            error (ruleCompiler_context, message, FATAL, 313);
                        }
                    } else {
                        // make sure we mark it as NOT an each!
                        tree_setKids (tree_kids[parsedActualsKP], nilKid);
                    }

                    rule_setLocalType (r->localVars.localsBase + actualCount, effectiveType);

                } else {
                    // it's a literal
                    const enum treeKindT literalKind = txltree_literal_kindT (tree_plural_firstTP (literalsTP));

                    if ((literalKind == treeKind_id) && (!txltree_isQuotedLiteral (tree_plural_firstTP (literalsTP)))) {
                        string message;
                        stringprintf (message, "Literal actual parameter '%s' of rule/function '%s' is not quoted", 
                            *ident_idents[actualRawName],
                            *ident_idents[r->name]);
                        error (ruleCompiler_context, message, WARNING, 307);
                    }

                    tree_setKind (tree_kids[parsedActualsKP], literalKind);

                    const tokenT literalType = tree_literalTypeName (tree_trees[tree_kids[parsedActualsKP]].kind);
                    rule_setLocalType (r->localVars.localsBase + actualCount, literalType);

                    if (eaching) {
                        // we're in the scope of an 'each' - so a literal can't be right!
                        string message;
                        stringprintf (message, "'each' argument of rule/function '%s' is not a list or repeat", 
                            *ident_idents[r->name]);
                        error (ruleCompiler_context, message, FATAL, 305);
                    }
                }

                literalsTP = tree_plural_restTP (literalsTP);
                if (tree_plural_emptyP (literalsTP)) break;

                parsedActualsKP = tree_newKid ();
            }

            // mark end of actuals with nilTree
            parsedActualsKP = tree_newKid ();
            tree_setKidTree (parsedActualsKP, nilTree);
        }

        rule_setNFormals (ruleIndex, actualCount);
        rule_setNPreLocals (ruleIndex, actualCount);
        rule_setNLocals (ruleIndex, actualCount);

        // already checked above
        rule_incFormalCount (r->localVars.nformals);
    }

    rule_setCalled (ruleIndex, true);
}


// Try to minimize warning messages
static int ruleCompiler_lastWarningTokensTP;

static void ruleCompiler_parseVarOrExp (const treePT patternTokensTP, struct ruleLocalsT *varsSoFar, const treePT productionTP, 
    treePT *parseTP, bool *isVarOrExp, bool *varOrExpMatches) 
{
    // Parse a local variable binding or reference (patternTokensTP) in a pattern or replacement.

    // Given a local variable binding (treeKindT.firstTime, e.g. X[T]), 
    // reference (treeKindT.subsequentUse or treeKindT.expression), or potential reference (treeKindT.literal), 
    // determine if it really is a local variable reference (isVarOrExp), 
    // and whether it matches the production nonterminal type (varOrExpMatches).

    // If so, return its parse node (parseTP) and enter or bind it to the corresponding local variable (in varsSoFar). 

    if (patternTokensTP == emptyTP) {
        *isVarOrExp = false;
        return;
    }

    // Case 1: A literal identifier in a pattern or replacement
    //    may be a context-dependent reference to a local variable

    if (stringcmp (*ident_idents[tree_trees[patternTokensTP].name], "TXL_literal_") == 0) {

        // May not be a literal: could be a subsequent use of a local variable
        const int localIndex = rule_lookupLocalVar ("", varsSoFar, txltree_literal_tokenT (patternTokensTP));

        if (localIndex == NOT_FOUND) {
            // It really was a literal after all
            *isVarOrExp = false;

            if (!txltree_isQuotedLiteral (patternTokensTP)) {
                // Warn if it is a type name, possibly an unintended error
                const tokenT terminalT = txltree_literal_tokenT (patternTokensTP);
                const int terminalIndex = symbol_lookupSymbol (terminalT);

                if ((terminalIndex != NOT_FOUND) && (ruleCompiler_lastWarningTokensTP != patternTokensTP)) {
                    string message;
                    stringprintf (message, "Type name '%s' used as a literal identifier (use [%s] or '%s instead)", 
                        *ident_idents[terminalT],
                        *ident_idents[terminalT],
                        *ident_idents[terminalT]);
                    error (ruleCompiler_context, message, WARNING, 315);
                    ruleCompiler_lastWarningTokensTP = patternTokensTP;
                }
            }

            return;
        }

        if (txltree_isQuotedLiteral (patternTokensTP)) {
            // If it's quoted it really is a literal after all 
            *isVarOrExp = false;

            // Warn if it's also a local variable name, possibly unintended error 
            if (ruleCompiler_lastWarningTokensTP != patternTokensTP) {
                string message;
                stringprintf (message, "Variable name '%s' is quoted as a literal identifier (possibly by mistake?)", 
                    *ident_idents[txltree_literal_tokenT (patternTokensTP)]);
                error (ruleCompiler_context, message, WARNING, 316);
                ruleCompiler_lastWarningTokensTP = patternTokensTP;
            }

            return;
        }

        // OK, it's not a literal, it really is a reference to a local variable
        *isVarOrExp = true;

        if (tree_treeIsTypeP (productionTP, rule_ruleLocals[varsSoFar->localsBase + localIndex].typename_)) {
            *varOrExpMatches = true;

            // Successful parse of a local variable reference
            const tokenT localName = rule_ruleLocals[varsSoFar->localsBase + localIndex].name;
            *parseTP = tree_newTreeInit (treeKind_subsequentUse, localName, localName, localIndex, nilKid);

            // Note: pattern subsequent uses to not count as references!

        } else {
            // It's a local variable reference, but doesn't match the production type, so parse fails
            *varOrExpMatches = false;
        }

    // Case 2: A binding occurence of a local variable in a pattern (e.g., X[T])

    } else if (stringcmp (*ident_idents[tree_trees[patternTokensTP].name], "TXL_firstTime_") == 0) {

        *isVarOrExp = true;

        tokenT firstTimeName = txltree_firstTime_nameT (patternTokensTP);

        if (firstTimeName == anonymous_T) {
            // If it's the anonymous variable, generate a unique name for it
            string anonymousName;
            stringprintf (anonymousName, "_anonymous_%d", varsSoFar->nlocals + 1);
            firstTimeName = ident_install (anonymousName, treeKind_id);
        }

        // Enter it in the rule's local variables
        const int localIndex = rule_enterLocalVar (ruleCompiler_context, varsSoFar, firstTimeName, txltree_firstTime_typeT (patternTokensTP));

        // Check that its production type is defined
        symbol_findSymbol (rule_ruleLocals[varsSoFar->localsBase + localIndex].typename_);

        // Does it match the production nonterminal type?
        if (tree_treeIsTypeP (productionTP, rule_ruleLocals[varsSoFar->localsBase + localIndex].typename_)) {
            *varOrExpMatches = true;

            // Successful parse of a local variable binding
            const tokenT localName = rule_ruleLocals[varsSoFar->localsBase + localIndex].name;
            *parseTP = tree_newTreeInit (treeKind_firstTime, localName, localName, localIndex, nilKid);

        } else {
            // It's a local variable binding, but it doesn't match the production type, so parse fails
            *varOrExpMatches = false;
            rule_unenterLocalVar (ruleCompiler_context, varsSoFar, firstTimeName);
        }

    // Case 3: A reference to a local variable in a replacement, possibly with rule calls 

    } else if (stringcmp (*ident_idents[tree_trees[patternTokensTP].name], "TXL_expression_") == 0) {

        // In a replacement, a reference to a local variable identifier gets parsed as a treeKindT.expression
        // If it's not a defined local variable, it may be a literal identifier

        const int localIndex = rule_lookupLocalVar ("", varsSoFar, txltree_expression_baseT (patternTokensTP));

        if (localIndex == NOT_FOUND) {
            // It's a literal, not a variable reference
            *isVarOrExp = false;

            // Check for rule calls
            if (!tree_plural_emptyP (txltree_expression_ruleCallsTP (patternTokensTP))) {
                // Rule calls on a literal!
                // We force a syntax error by pretending it is a variable reference that did not match
                *isVarOrExp = true;
                *varOrExpMatches = false;
            }

            if (!txltree_isQuotedLiteral (patternTokensTP)) {
                // Warn if it is a type name, possibly unintended error
                const tokenT terminalT = txltree_literal_tokenT (patternTokensTP);
                const int terminalIndex = symbol_lookupSymbol (terminalT);

                if ((terminalIndex != NOT_FOUND) && (ruleCompiler_lastWarningTokensTP != patternTokensTP)) {
                    string message;
                    stringprintf (message, "Type name '%s' used as a literal identifier (use [%s] or '%s instead)", 
                        *ident_idents[terminalT],
                        *ident_idents[terminalT],
                        *ident_idents[terminalT]);
                    error (ruleCompiler_context, message, WARNING, 315);
                    ruleCompiler_lastWarningTokensTP = patternTokensTP;
                }
            }

            return;
        }

        // OK, it's not a literal, it really is a reference to a local variable
        *isVarOrExp = true;

        // Does it match the production nonterminal type?
        const tokenT localVarType = rule_ruleLocals[varsSoFar->localsBase + localIndex].typename_;

        if (tree_treeIsTypeP (productionTP, localVarType)) {
            *varOrExpMatches = true;

            // Successful parse of a local variable reference in a replacement
            const tokenT expName = txltree_expression_baseT (patternTokensTP);
            *parseTP = tree_newTreeInit (treeKind_expression, expName, expName, localIndex, nilKid);  // save looking for it later

            // Counts as a use of the variable
            rule_incLocalRefs (varsSoFar->localsBase + localIndex, 1);
            rule_setLocalLastRef (varsSoFar->localsBase + localIndex, *parseTP);

            // A local variable reference in a replacement may have subrule calls (e.g., X[R1][R2]) 
            // Make children of type ruleCall
            treePT ruleCallsTP = txltree_expression_ruleCallsTP (patternTokensTP);
            const treePT ruleCallsTPcopy = ruleCallsTP;

            // Are there any rule calls?
            if (!tree_plural_emptyP (ruleCallsTP)) {
                // If so, remember that they act on the local variable
                rule_setLocalChanged (varsSoFar->localsBase + localIndex, true);

                // Pre-allocate the rule call kids to keep them contiguous for speed when transforming
                int nkids = 1;
                while (true) {
                    ruleCallsTP = tree_plural_restTP (ruleCallsTP);
                    if (tree_plural_emptyP (ruleCallsTP)) break;
                    nkids += 1;
                }

                kidPT lastKidKP = tree_newKids (nkids + 1);  // (sic) 
                tree_setKids (*parseTP, lastKidKP);

                // Mark the end of the rule calls with a nilTree
                tree_setKidTree (lastKidKP + nkids, nilTree);

                // Now fill in the kids we allocated with the rule calls
                ruleCallsTP = ruleCallsTPcopy;

                for (int k = 1; k <= nkids; k++) {
                    treePT parsedCallTP;
                    ruleCompiler_processRuleCall (localVarType, tree_plural_firstTP (ruleCallsTP), varsSoFar, &parsedCallTP, false);
                    tree_setKidTree (lastKidKP, parsedCallTP);
                    ruleCallsTP = tree_plural_restTP (ruleCallsTP);
                    lastKidKP += 1;
                }
                assert (tree_kids[lastKidKP] == nilTree);
            }

        } else {
            // It's a local variable reference, but it doesn't match the production type, so parse fails
            *varOrExpMatches = false;
        }

    } else {
        error (ruleCompiler_context, "Fatal TXL error in parseVarOrExp", INTERNAL_FATAL, 318);
    }
}

static void ruleCompiler_parsePattern (treePT arg_litsAndVarsAndExpsTP, struct ruleLocalsT *varsSoFar, treePT productionTP, treePT *parseTP)
{
    // Initialize the pattern's input tokens for parsing
    treePT litsAndVarsAndExpsTP = arg_litsAndVarsAndExpsTP;
    lastTokenIndex = 0;
    while (true) {
        lastTokenIndex += 1;

        if (lastTokenIndex > maxPatternTokens) break;

        if (tree_plural_emptyP (litsAndVarsAndExpsTP)) break;

        struct tokenTableT *inputToken = &(inputTokens[lastTokenIndex]);
        inputToken->tree = tree_kid1TP (tree_plural_firstTP (litsAndVarsAndExpsTP));
        inputToken->token = txltree_literal_tokenT ((inputTokens[lastTokenIndex].tree));
        inputToken->rawtoken = txltree_literal_rawtokenT ((inputTokens[lastTokenIndex].tree));
        inputToken->kind = txltree_literal_kindT ((inputTokens[lastTokenIndex].tree));

        // A token may have been an id or keyword when parsed as TXL,
        // but what it is in the object language may be different!
        if ((inputToken->kind == treeKind_id) || (inputToken->kind == treeKind_key)) {
            if (scanner_keyP (inputToken->token)) {
                // this language thinks it's a keyword 
                inputToken->kind = treeKind_key;
            } else {
                // nope, just a normal id
                inputToken->kind = treeKind_id;
            }
        }

        litsAndVarsAndExpsTP = tree_plural_restTP (litsAndVarsAndExpsTP);
    }

    if (lastTokenIndex > maxPatternTokens) {
        string message;
        stringprintf (message, "Pattern or replacement too large (> %d tokens)", maxPatternTokens);
        error (ruleCompiler_context, message, LIMIT_FATAL, 319);
    }

    struct tokenTableT *inputToken = &(inputTokens[lastTokenIndex]);
    inputToken->tree = emptyTP;
    inputToken->token = empty_T;
    inputToken->rawtoken = empty_T;
    inputToken->kind = treeKind_empty;

    if (options_option[tree_print_p]) {
        fprintf (stderr, "\n");
    }

    parser_initializeParse (ruleCompiler_context, false, true, false, varsSoFar, ruleCompiler_parseVarOrExp);
    parser_parse (productionTP, parseTP);

    if (*parseTP == nilTree) {
        patternError (failTokenIndex, ruleCompiler_context, productionTP);
    }

    if (options_option[pattern_print_p]) {
        string pcontext;
        stringcpy (pcontext, ruleCompiler_context);
        while (true) {
            const int qindex = stringindex (pcontext, "'");
            if (qindex == 0) break;
            string temp1, temp2;
            substring (temp1, pcontext, 1, qindex - 1);
            substring (temp2, pcontext, qindex + 1, stringlen (pcontext));
            stringcpy (pcontext, temp1), stringcat (pcontext, "\""), stringcat (pcontext, temp2);
        }
        fprintf (stderr, "----- Parse Tree for %s -----\n", pcontext);
        unparser_printPatternParse (*parseTP, varsSoFar, 0);
        fprintf (stderr, "----- End Parse Tree -----\n\n");
    }
}

static void ruleCompiler_processPatternOrReplacement (tokenT goalName, treePT patternOrReplacementTP, treePT *parseTP, struct ruleLocalsT *varsSoFar)
{
    // This is designed to work for both patterns and replacements
    const treePT litsAndVarsAndExpsTP = txltree_patternOrReplacement_litsAndVarsAndExpsTP (patternOrReplacementTP);
    const int symbolIndex = symbol_findSymbol (goalName);
    const treePT goalTP = symbol_symbols[symbolIndex];

    ruleCompiler_parsePattern (litsAndVarsAndExpsTP, varsSoFar, goalTP, parseTP);
}

static void ruleCompiler_processConstruct (tokenT ruleNameT, treePT constructTP, rulePartsBaseT partIndex, struct ruleLocalsT *localVars)
{
    rule_setPartKind (partIndex, rulePart_construct);
    tokenT nameT = txltree_construct_varNameT (constructTP);
    rule_setPartName (partIndex, nameT);

    stringprintf (ruleCompiler_context, "construct '%s' of rule/function '%s'", *ident_idents[nameT], 
        *ident_idents[ruleNameT]);

    if (nameT == anonymous_T) {
        string anonName;
        stringprintf (anonName, "_%d_", localVars->nlocals + 1);
        nameT = ident_install (anonName, treeKind_id);
    }

    // lookup name in VarsSo far.  If it's there, then it's an error
    int localIndex = rule_lookupLocalVar (ruleCompiler_context, localVars, nameT);

    if (localIndex != NOT_FOUND) {
        error (ruleCompiler_context, "Constructed variable has already been defined", FATAL, 320);
    }

    const tokenT targetT = txltree_construct_targetT (constructTP);
    rule_setPartTarget (partIndex, targetT);

    const treePT replacementTP = txltree_construct_replacementTP (constructTP);

    treePT resultTP;
    ruleCompiler_processPatternOrReplacement (targetT, replacementTP, &resultTP, localVars);
    rule_setPartReplacement (partIndex, resultTP);

    // now enter variable in localVars
    localIndex = rule_enterLocalVar (ruleCompiler_context, localVars, nameT, targetT);
    rule_setPartNameRef (partIndex, localIndex);
}

static void ruleCompiler_makeAnonymousConstruct (tokenT targetT, rulePartsBaseT partIndex, struct ruleLocalsT *localVars)
{
    // create a new anonymous local construct as a parse of [empty]

    // create new anonymous local variable
    string anonName;
    stringprintf (anonName, "_anonymous_%d", localVars->nlocals + 1);
    const tokenT anonT = ident_install (anonName, treeKind_id);

    rule_setPartKind (partIndex, rulePart_construct);
    rule_setPartName (partIndex, anonT);
    rule_setPartTarget (partIndex, targetT);

    const int localIndex = rule_enterLocalVar (ruleCompiler_context, localVars, anonT, targetT);
    rule_setPartNameRef (partIndex, localIndex);

    // make a fake TXL replacement parse to be the value
    const treePT replacementTP = tree_newTree ();
    const treePT expsAndLitsTP = tree_newTree ();

    const tokenT TXLreplacementT = ident_install ("TXL_replacement_", treeKind_id);
    const tokenT TXLexpsAndLitsT = ident_install ("TXL_expsAndLits_", treeKind_id);

    tree_setKind (replacementTP, treeKind_choose);
    tree_setName (replacementTP, TXLreplacementT);
    tree_setRawName (replacementTP, TXLreplacementT);
    kidPT newKid = tree_newKid ();
    tree_setKidTree (newKid, expsAndLitsTP);
    tree_setKids (replacementTP, newKid);

    tree_setKind (expsAndLitsTP, treeKind_choose);
    tree_setName (expsAndLitsTP, TXLexpsAndLitsT);
    tree_setRawName (expsAndLitsTP, TXLexpsAndLitsT);
    newKid = tree_newKid ();
    tree_setKids (expsAndLitsTP, newKid);

    // make the appropriate default value -
    // for [number], it is 0, for [id] or [comment], it is _,
    // for [stringlit], it is "", for [charlit], it is ''
    // for any other type it is [empty]
    treePT defaultTP = emptyTP;

    if (typeKind (targetT) != treeKind_undefined) {
        // build a phoney TXL parse of a literal of the appropriate kind

        // names of the TXL replacement parse nodes
        const tokenT TXLindExpsAndLitsT = ident_lookup ("TXL_indExpsAndLits_");
        const tokenT TXLexpOrLitT = ident_lookup ("TXL_expOrLit_");
        const tokenT TXLliteralT = ident_lookup ("TXL_literal_");
        assert ((TXLindExpsAndLitsT != NOT_FOUND) && (TXLexpOrLitT != NOT_FOUND) && (TXLliteralT != NOT_FOUND));

        // make a TXL replacement tree
        newKid = tree_newKid ();
        tree_setKidTree (newKid, emptyTP);
        const treePT emptyExpsAndLitsTP = tree_newTreeInit (treeKind_choose, TXLexpsAndLitsT, TXLexpsAndLitsT, 1, newKid);

        const kidPT expOrLitKidKP = tree_newKid ();
        // kid tree to be filled in below
        const treePT expOrLitTP = tree_newTreeInit (treeKind_choose, TXLexpOrLitT, TXLexpOrLitT, 1, expOrLitKidKP);

        const kidPT newKids = tree_newKids (2);
        tree_setKidTree (newKids, expOrLitTP);
        tree_setKidTree (newKids + 1, emptyExpsAndLitsTP);
        const treePT indExpsAndLitsTP = tree_newTreeInit (treeKind_order, TXLindExpsAndLitsT, TXLindExpsAndLitsT, 2, newKids);

        // it only remains to fill in  tree.kids (expOrLitKidKP)
        // with the literal or id expression for the default 
        if ((typeKind (targetT) >= firstLeafKind) && (typeKind (targetT) <= lastLeafKind)) {

            const treePT tokenTP = tree_newTree ();
            // real kind and value (.name) filled in below, depending on kind 

            newKid = tree_newKid ();
            tree_setKidTree (newKid, tokenTP);

            const treePT literalTP = tree_newTreeInit (treeKind_choose, TXLliteralT, TXLliteralT, 1, newKid);

            if (targetT == stringlit_T) {
                tree_setKind (tokenTP, treeKind_stringlit);
                const tokenT tokenName = ident_install ("\"\"", treeKind_stringlit);
                tree_setName (tokenTP, tokenName);
                tree_setRawName (tokenTP, tokenName);
            } else if (targetT == charlit_T) {
                tree_setKind (tokenTP, treeKind_charlit);
                const tokenT tokenName = ident_install ("''", treeKind_charlit);
                tree_setName (tokenTP, tokenName);
                tree_setRawName (tokenTP, tokenName);
            } else if ((targetT == number_T) || (targetT == floatnumber_T) || (targetT == decimalnumber_T) || (targetT == integernumber_T)) {
                // kind must be [number] for all of them!
                tree_setKind (tokenTP, treeKind_number);
                const tokenT tokenName = ident_install ("0", treeKind_number);
                tree_setName (tokenTP, tokenName);
                tree_setRawName (tokenTP, tokenName);
            } else {
                tree_setKind (tokenTP, typeKind (targetT));
                const tokenT tokenName = ident_install ("", treeKind_id);
                tree_setName (tokenTP, tokenName);
                tree_setRawName (tokenTP, tokenName);
            }

            tree_setKidTree (expOrLitKidKP, literalTP);

        } else {
            string message;
            stringprintf (message, "Anonymous construct/replacement cannot be of type [%s]", *ident_idents[targetT]);
            error (ruleCompiler_context, message, FATAL, 322);
        }

        defaultTP = indExpsAndLitsTP;
    }

    tree_setKidTree (tree_trees[expsAndLitsTP].kidsKP, defaultTP);

    // build a parse of the fake replacement as the value of the variable
    treePT resultTP;
    ruleCompiler_processPatternOrReplacement (targetT, replacementTP, &resultTP, localVars);
    rule_setPartReplacement (partIndex, resultTP);
}

static void ruleCompiler_processConstructAnonymous (tokenT ruleNameT, treePT constructOrExportTP, rulePartsBaseT partIndex, struct ruleLocalsT *localVars)
{
    // create a new anonymous local construct as a parse of [empty], 
    // and replace the original anonymous variable in the real construct
    // with the new anonymous local
    string partName;
    stringcpy (partName, *ident_idents[tree_trees[constructOrExportTP].name]);
    assert ((stringcmp (partName, "TXL_constructPart_") == 0) || (stringcmp (partName, "TXL_exportPart_") == 0));

    const tokenT nameT = txltree_construct_varNameT (constructOrExportTP);

    if (stringcmp (partName, "TXL_constructPart_") == 0) {
        stringprintf (ruleCompiler_context, "construct '%s' of rule/function '%s'", *ident_idents[nameT],
            *ident_idents[ruleNameT]);
    } else {
        stringprintf (ruleCompiler_context, "export '%s' of rule/function '%s'", *ident_idents[nameT],
            *ident_idents[ruleNameT]);
    }

    // the target of the anonymous construct is the same as the target of the real construct
    tokenT targetT;
    if (stringcmp (partName, "TXL_constructPart_") == 0) {
        targetT = txltree_construct_targetT (constructOrExportTP);
    } else {
        const int localIndex = rule_lookupLocalVar (ruleCompiler_context, localVars, nameT);
        targetT = txltree_import_export_targetT (constructOrExportTP);

        if (targetT == NOT_FOUND) {
            if (localIndex != NOT_FOUND) {
                targetT = rule_ruleLocals[localVars->localsBase + localIndex].typename_;
            } else {
                error (ruleCompiler_context, "Type required for exported variable", FATAL, 321);
            }
        } else {
            if (localIndex != NOT_FOUND) {
                // (warning for this will be given by processExport)
                targetT = rule_ruleLocals[localVars->localsBase + localIndex].typename_;
            }
        }
    }

    // create the actual anonymous construct of that type 
    ruleCompiler_makeAnonymousConstruct (targetT, partIndex, localVars);

    // make a reference for the new local and replace the anonymous
    // with it in the real construct
    const treePT anonTP = tree_newTreeInit (treeKind_id, rule_ruleParts[partIndex].name, rule_ruleParts[partIndex].name, 0, nilKid);

    // replace the anonymous in the real construct with the new local
    const treePT anonymousExpressionTP = txltree_construct_anonymousExpressionTP (constructOrExportTP);

    assert (tree_trees[tree_kid1TP (anonymousExpressionTP)].name == anonymous_T);
    tree_setKidTree (tree_trees[anonymousExpressionTP].kidsKP, anonTP);
}

static void ruleCompiler_processDeconstruct ( tokenT ruleNameT, treePT deconstructTP, rulePartsBaseT partIndex, struct ruleLocalsT *localVars)
{
    rule_setPartKind (partIndex, rulePart_deconstruct);
    const tokenT nameT = txltree_deconstruct_varNameT (deconstructTP);
    rule_setPartName (partIndex, nameT);

    stringprintf (ruleCompiler_context, "deconstruct '%s' of rule/function '%s'", *ident_idents[nameT],
            *ident_idents[ruleNameT]);

    // lookup name in varsSoFar - it must be there if we're deconstructing it!
    const int localIndex = rule_findLocalVar (ruleCompiler_context, localVars, nameT);

    const int oldVarCount = localVars->nlocals;

    // deconstruct itself counts as a reference
    rule_incLocalRefs (localVars->localsBase + localIndex, 1);

    rule_setPartNameRef (partIndex, localIndex);
    rule_setPartStarred (partIndex, txltree_deconstruct_isStarred (deconstructTP));

    tokenT targetT = rule_ruleLocals[localVars->localsBase + localIndex].typename_;

    if (txltree_deconstruct_isTyped (deconstructTP)) {
        // search is explicitly typed
        targetT = txltree_deconstruct_targetT (deconstructTP);

        // warn if we can't get a match
        if ((targetT != rule_ruleLocals[localVars->localsBase + localIndex].typename_) 
                && (rule_ruleLocals[localVars->localsBase + localIndex].typename_ != any_T) 
                && (!(rule_ruleParts[partIndex].starred))) {
            error (ruleCompiler_context, "Typed deconstruct can never match", WARNING, 323);
        }
    }
    rule_setPartTarget (partIndex, targetT);

    // process skipping
    const treePT optSkippingTP = txltree_deconstruct_optSkippingTP (deconstructTP);

    rule_setPartSkipName (partIndex, NOT_FOUND);
    rule_setPartSkipName (partIndex, NOT_FOUND);
    rule_setPartSkipName (partIndex, NOT_FOUND);

    if (! tree_plural_emptyP (optSkippingTP)) {
        tokenT skippingNameT = txltree_optSkippingNameT (optSkippingTP, 1);
        rule_setPartSkipName (partIndex, skippingNameT);
        // Check that the skipped production has been defined
        symbol_findSymbol (rule_ruleParts[partIndex].skipName);

        // Is there a second one?
        skippingNameT = txltree_optSkippingNameT (optSkippingTP, 2);

        if (skippingNameT != NOT_FOUND) {
            rule_setPartSkipName (partIndex, skippingNameT);
            // Check that the skipped production has been defined
            symbol_findSymbol (rule_ruleParts[partIndex].skipName);

            // How about a third one?
            skippingNameT = txltree_optSkippingNameT (optSkippingTP, 3);

            if (skippingNameT != NOT_FOUND) {
                rule_setPartSkipName (partIndex, skippingNameT);
                // Check that the skipped production has been defined
                symbol_findSymbol (rule_ruleParts[partIndex].skipName);
            }

        } else {
            if ((rule_ruleParts[partIndex].skipName == targetT) 
                    && tree_isListOrRepeatType (rule_ruleLocals[localVars->localsBase + localIndex].typename_) 
                    && (targetT == tree_listOrRepeatBaseType (rule_ruleLocals[localVars->localsBase + localIndex].typename_))) {
                // skipping [X] deconstruct * [X] V [repeat/list X]
                rule_setPartSkipRepeat (partIndex, true);

            } else {
                rule_setPartSkipRepeat (partIndex, false);
            }
        }
    }

    const treePT patternTP = txltree_deconstruct_patternTP (deconstructTP);

    treePT resultTP;
    ruleCompiler_processPatternOrReplacement (targetT, patternTP, &resultTP, localVars);
    rule_setPartPattern (partIndex, resultTP);

    for (int newlocal = oldVarCount + 1; newlocal <= localVars->nlocals; newlocal++) {
        rule_setLocalPartOf (localVars->localsBase + newlocal, rule_ruleParts[partIndex].nameRef);
        rule_setLocalRefs (localVars->localsBase + newlocal, 0);
    }

    rule_setPartNegated (partIndex, txltree_deconstruct_negated (deconstructTP));

    if (rule_ruleParts[partIndex].negated) {
        // all the bound variables are really anonymous, since they don't exist after the deconstruct
        for (int newlocal = oldVarCount + 1; newlocal <= localVars->nlocals; newlocal++) {
            string anonName;
            stringprintf (anonName, "_anonymous_%d", newlocal);
            const tokenT anonT = ident_install (anonName, treeKind_id);
            rule_setLocalName (localVars->localsBase + newlocal, anonT);
            rule_setLocalRefs (localVars->localsBase + newlocal, 0);
        }
    }

    if ((localVars->nlocals == oldVarCount) || (rule_ruleParts[partIndex].negated)) {
        // a trivial deconstruct that binds no new variables -
        // in this case, we need not count the deconstruct as a reference,
        // if this is the first use of the deconstructed variable!
        if (rule_ruleLocals[localVars->localsBase + localIndex].refs == 1) {
            rule_setLocalRefs (localVars->localsBase + localIndex, 0);
        }
    }
}

static void ruleCompiler_processCondition (tokenT ruleNameT, treePT conditionTP, rulePartsBaseT partIndex, struct ruleLocalsT *localVars)
{
    const treePT expressionTP = txltree_condition_expressionTP (conditionTP);

    if (txltree_condition_is_assert (conditionTP)) {
        rule_setPartKind (partIndex, rulePart_assert);
    } else {
        rule_setPartKind (partIndex, rulePart_cond);
    }

    const tokenT nameT = txltree_expression_baseT (expressionTP);
    rule_setPartName (partIndex, nameT);

    stringprintf (ruleCompiler_context, "where condition '%s' of rule/function '%s'", *ident_idents[nameT], 
        *ident_idents[ruleNameT]);

    // lookup name in varsSoFar - It must be there if we have a condition on it!
    const int localIndex = rule_findLocalVar (ruleCompiler_context, localVars, nameT);

    // condition (where) counts as a reference 
    rule_incLocalRefs (localVars->localsBase + localIndex, 1);

    rule_setPartNameRef (partIndex, localIndex);

    const tokenT targetT = rule_ruleLocals[localVars->localsBase + localIndex].typename_;
    rule_setPartTarget (partIndex, targetT);

    // OK, now we cheat like hell.  What we are going to do is to embed
    // the expression in an expsAndLitsAndVars tree so we can call
    // processPatternOrReplacement

    const treePT parseTP = tree_newTreeInit (treeKind_expression, nameT, nameT, localIndex, nilKid);

    // make kids of rule call
    treePT ruleCallsTP = txltree_expression_ruleCallsTP (expressionTP);
    if (tree_plural_emptyP (ruleCallsTP)) {
        error (ruleCompiler_context, "'where' condition requires a rule call", FATAL, 324);
    }

    const treePT ruleCallsTPcopy = ruleCallsTP;

    // pre-allocate the kids to keep them contiguous
    int nkids = 1;
    while (true) {
        ruleCallsTP = tree_plural_restTP (ruleCallsTP);
        if (tree_plural_emptyP (ruleCallsTP)) break;
        nkids += 1;
    }

    kidPT lastKidKP = tree_newKids ((nkids + 1));
    tree_setKids (parseTP, lastKidKP);

    // mark the end of the list with a nilTree
    tree_setKidTree (lastKidKP + nkids, nilTree);

    // now fill in the kids
    ruleCallsTP = ruleCallsTPcopy;
    for (int k = 1; k <= nkids; k++) {
        treePT parsedCallTP;
        ruleCompiler_processRuleCall (targetT, tree_plural_firstTP (ruleCallsTP), localVars, &parsedCallTP, true);
        tree_setKidTree (lastKidKP, parsedCallTP);
        ruleCallsTP = tree_plural_restTP (ruleCallsTP);
        lastKidKP += 1;
    }
    assert (tree_kids[lastKidKP] == nilTree);

    rule_setPartReplacement (partIndex, parseTP);

    rule_setPartNegated (partIndex, txltree_condition_negated (conditionTP));
    rule_setPartAnded (partIndex, txltree_condition_anded (conditionTP));
}

static void ruleCompiler_processConditionAnonymous (tokenT ruleNameT, treePT conditionTP, rulePartsBaseT partIndex, struct ruleLocalsT *localVars)
{
    // create a new anonymous local construct as a parse of [empty], 
    // and replace the original anonymous variable in the condition
    // with the new anonymous local

    string partName;
    stringcpy (partName, *ident_idents[tree_trees[conditionTP].name]);
    assert (stringcmp (partName, "TXL_conditionPart_") == 0);

    // create an anonymous construct of type [empty]
    ruleCompiler_makeAnonymousConstruct (id_T, partIndex, localVars);

    // make a reference for the new local and replace the anonymous
    // with it in the real construct
    const treePT anonTP = tree_newTreeInit (treeKind_id, (rule_ruleParts[partIndex].name), (rule_ruleParts[partIndex].name), 0, nilKid);

    // replace the anonymous in the real construct with the new local
    const treePT anonymousExpressionTP = txltree_condition_expressionTP (conditionTP);
    assert (tree_trees[tree_kid1TP (anonymousExpressionTP)].name == anonymous_T);
    tree_setKidTree (tree_trees[anonymousExpressionTP].kidsKP, anonTP);
}

static void ruleCompiler_processImport (tokenT ruleNameT, treePT importTP, rulePartsBaseT partIndex, struct ruleLocalsT *localVars)
{
    const tokenT nameT = txltree_construct_varNameT (importTP);

    rule_setPartKind (partIndex, rulePart_import);
    rule_setPartName (partIndex, nameT);

    stringprintf (ruleCompiler_context, "import '%s' of rule/function '%s'", *ident_idents[nameT], 
        *ident_idents[ruleNameT]);

    // lookup name in localVars so far.  If it's there, then it's an error
    int localIndex = rule_lookupLocalVar (ruleCompiler_context, localVars, nameT);
    if ((localIndex != NOT_FOUND) && (!(rule_ruleLocals[localVars->localsBase + localIndex].global))) {
        error (ruleCompiler_context, "Imported variable has already been defined", FATAL, 325);
    }

    // find the target type of the import
    tokenT targetT = txltree_import_export_targetT (importTP);

    if (targetT == NOT_FOUND) {
        if (localIndex != NOT_FOUND) {
            targetT = rule_ruleLocals[localVars->localsBase + localIndex].typename_;
        } else {
            error (ruleCompiler_context, "Type required for imported variable", FATAL, 326);
        }
    } else {
        if (localIndex != NOT_FOUND) {
            error (ruleCompiler_context, "Imported variable already has a type (import type ignored)", WARNING, 327);
            targetT = rule_ruleLocals[localVars->localsBase + localIndex].typename_;
        }
    }

    rule_setPartTarget (partIndex, targetT);

    // process pattern, if any
    const treePT patternTP = txltree_import_patternTP (importTP);
    const int oldVarCount = localVars->nlocals;

    if (tree_plural_emptyP (tree_kid1TP (patternTP))) {
        rule_setPartPattern (partIndex, 0);
    } else {
        treePT resultTP;
        ruleCompiler_processPatternOrReplacement (targetT, patternTP, &resultTP, localVars);
        rule_setPartPattern (partIndex, resultTP);
    }

    // now enter the variable in localVars
    if (localIndex == NOT_FOUND) {
        localIndex = rule_enterLocalVar (ruleCompiler_context, localVars, nameT, targetT);
        rule_setLocalGlobal (localVars->localsBase + localIndex, true);
    }
    rule_setPartNameRef (partIndex, localIndex);

    // mark any deconstructed parts as parts of this import
    for (int newlocal = oldVarCount + 1; newlocal <= localVars->nlocals; newlocal++) {
        if (newlocal != localIndex) {
            rule_setLocalPartOf (localVars->localsBase + newlocal, rule_ruleParts[partIndex].nameRef);
            rule_setLocalRefs (localVars->localsBase + newlocal, 0);
        }
    }

    // we start each import with TWO references to account for its
    // probable use elsewhere
    rule_setLocalRefs (localVars->localsBase + localIndex, 2);
}

static void ruleCompiler_processExport (tokenT ruleNameT, treePT exportTP, rulePartsBaseT partIndex, struct ruleLocalsT *localVars)
{
    const tokenT nameT = txltree_construct_varNameT (exportTP);

    rule_setPartKind (partIndex, rulePart_export);
    rule_setPartName (partIndex, nameT);

    stringprintf (ruleCompiler_context, "export '%s' of rule/function '%s'", *ident_idents[nameT], 
        *ident_idents[ruleNameT]);

    // lookup name in localVars so far
    int localIndex = rule_lookupLocalVar (ruleCompiler_context, localVars, nameT);

    // find the target type of the export
    tokenT targetT = txltree_import_export_targetT (exportTP);

    if (targetT == NOT_FOUND) {
        if (localIndex != NOT_FOUND) {
            targetT = rule_ruleLocals[localVars->localsBase + localIndex].typename_;
        } else {
            error (ruleCompiler_context, "Type required for exported variable", FATAL, 328);
        }
    } else {
        if (localIndex != NOT_FOUND) {
            error (ruleCompiler_context, "Exported variable already has a type (export type ignored)", WARNING, 329);
            targetT = rule_ruleLocals[localVars->localsBase + localIndex].typename_;
        }
    }

    rule_setPartTarget (partIndex, targetT);

    // process replacement, if any
    const treePT replacementTP = txltree_construct_replacementTP (exportTP);

    if (tree_plural_emptyP (tree_kid1TP (replacementTP))) {
        if (localIndex == NOT_FOUND) {
            error (ruleCompiler_context, "Exported variable has not been bound (export value required)", FATAL, 330);
        } else {
            rule_setPartReplacement (partIndex, nilTree);
        }
    } else {
        treePT resultTP;
        ruleCompiler_processPatternOrReplacement (targetT, replacementTP, &resultTP, localVars);
        rule_setPartReplacement (partIndex, resultTP);
        if (localIndex == NOT_FOUND) {
            localIndex = rule_enterLocalVar (ruleCompiler_context, localVars, nameT, targetT);
        }
    }

    // even if it wasn't global before, it is now!
    rule_setLocalGlobal (localVars->localsBase + localIndex, true);

    rule_setPartNameRef (partIndex, localIndex);

    // we start each export with one reference to account for its probable use elsewhere.
    // if it was already bound, then we just increment its count
    rule_incLocalRefs (localVars->localsBase + localIndex, 1);
}

static void ruleCompiler_makeDefaultMatchPart (treePT ruleTP)
{
    // In TXL 11.1, match/replace parts are optional, to assist in writing utility rules.
    // The default is a pattern that matches anything:
    //
    //  match [any]
    //      _ [any] 
    //
    // We implement this by constructing the TXL bootstrap parse of that pattern.

    // TXL_pattern order -> TXL_firstsAndLits choose -> TXL_indFirstsAndLits order -> 
    //  TXL_firstOrLit choose -> 
    //      (TXL_firstTime order -> 
    //          (id (_), empty ([), TXL_description choose -> id (any), empty (])), 
    //              TXL_firstsAndLits choose -> emptyTP)

    // The target type [any]
    const tokenT TXLdescriptionT = ident_install ("TXL_description_", treeKind_id);
    const treePT TXLdescription_anyTP = tree_newTreeInit (treeKind_choose, TXLdescriptionT, TXLdescriptionT, 0, nilKid);
    const treePT anyTP = tree_newTreeInit (treeKind_id, any_T, any_T, 0, nilKid);
    tree_makeOneKid (TXLdescription_anyTP, anyTP);

    const tokenT TXLbracketedDescriptionT = ident_install ("TXL_bracketedDescription_", treeKind_id);
    const treePT TXLbracketedDescription_anyTP = tree_newTreeInit (treeKind_order, TXLbracketedDescriptionT, TXLbracketedDescriptionT, 0, nilKid);
    tree_makeThreeKids (TXLbracketedDescription_anyTP, emptyTP, TXLdescription_anyTP, emptyTP);

    const tokenT TXLpatternT = ident_install ("TXL_pattern_", treeKind_id);
    const tokenT TXLfirstsAndLitsT = ident_install ("TXL_firstsAndLits_", treeKind_id);
    const tokenT TXLindFirstsAndLitsT = ident_install ("TXL_indFirstsAndLits_", treeKind_id);
    const tokenT TXLfirstOrLitT = ident_install ("TXL_firstOrLit_", treeKind_id);
    const tokenT TXLfirstTimeT = ident_install ("TXL_firstTime_", treeKind_id);

    const treePT TXLfirstTime_anyTP = tree_newTreeInit (treeKind_order, TXLfirstTimeT, TXLfirstTimeT, 0, nilKid);
    const treePT underscoreTP = tree_newTreeInit (treeKind_id, underscore_T, underscore_T, 0, nilKid);
    tree_makeFourKids (TXLfirstTime_anyTP, underscoreTP, emptyTP, TXLdescription_anyTP, emptyTP);

    const treePT TXLfirstOrLit_anyTP = tree_newTreeInit (treeKind_choose, TXLfirstOrLitT, TXLfirstOrLitT, 0, nilKid);
    tree_makeOneKid (TXLfirstOrLit_anyTP, TXLfirstTime_anyTP);

    const treePT TXLfirstsAndLits_emptyTP = tree_newTreeInit (treeKind_choose, TXLfirstsAndLitsT, TXLfirstsAndLitsT, 0, nilKid);
    tree_makeOneKid (TXLfirstsAndLits_emptyTP, emptyTP);

    const treePT TXLindFirstsAndLits_anyTP = tree_newTreeInit (treeKind_order, TXLindFirstsAndLitsT, TXLindFirstsAndLitsT, 0, nilKid);
    tree_makeTwoKids (TXLindFirstsAndLits_anyTP, TXLfirstOrLit_anyTP, TXLfirstsAndLits_emptyTP);

    const treePT TXLfirstsAndLits_anyTP = tree_newTreeInit (treeKind_choose, TXLfirstsAndLitsT, TXLfirstsAndLitsT, 0, nilKid);
    tree_makeOneKid (TXLfirstsAndLits_anyTP, TXLindFirstsAndLits_anyTP);

    const treePT TXLpattern_anyTP = tree_newTreeInit (treeKind_order, TXLpatternT, TXLpatternT, 0, nilKid);
    tree_makeOneKid (TXLpattern_anyTP, TXLfirstsAndLits_anyTP);

    // The match part match [any] _ [any]

    // TXL_replaceOrMatchPart order -> 
    //  (TXL_optSkippingBracketedDescription choose -> empty, 
    //      TXL_replaceOrMatch choose -> id (match), 
    //          TXL_optStarDollarHash choose -> empty, 
    //              TXL_bracketedDescription_anyTP, TXL_pattern_anyTP)

    const tokenT TXLreplaceOrMatchPartT = ident_install ("TXL_replaceOrMatchPart_", treeKind_id);
    const tokenT TXLoptSkippingBracketedDescriptionT = ident_install ("TXL_optSkippingBracketedDescription_", treeKind_id);
    const tokenT TXLreplaceOrMatchT = ident_install ("TXL_replaceOrMatch_", treeKind_id);
    const tokenT TXLoptStarDollarHashT = ident_install ("TXL_optStarDollarHash_", treeKind_id);

    const treePT TXLoptSkippingBracketedDescription_emptyTP = tree_newTreeInit (treeKind_choose, TXLoptSkippingBracketedDescriptionT, 
        TXLoptSkippingBracketedDescriptionT, 0, nilKid);
    tree_makeOneKid (TXLoptSkippingBracketedDescription_emptyTP, emptyTP);

    const treePT TXLreplaceOrMatch_matchTP = tree_newTreeInit (treeKind_choose, TXLreplaceOrMatchT, TXLreplaceOrMatchT, 0, nilKid);
    const treePT matchTP = tree_newTreeInit (treeKind_id, match_T, match_T, 0, nilKid);
    tree_makeOneKid (TXLreplaceOrMatch_matchTP, matchTP);

    const treePT TXLoptStarDollarHash_emptyTP = tree_newTreeInit (treeKind_choose, TXLoptStarDollarHashT, TXLoptStarDollarHashT, 0, nilKid);
    tree_makeOneKid (TXLoptStarDollarHash_emptyTP, emptyTP);

    const treePT TXLreplaceOrMatchPart_anyTP = tree_newTreeInit (treeKind_order, TXLreplaceOrMatchPartT, TXLreplaceOrMatchPartT, 0, nilKid);
    tree_makeFiveKids (TXLreplaceOrMatchPart_anyTP, TXLoptSkippingBracketedDescription_emptyTP, TXLreplaceOrMatch_matchTP, 
        TXLoptStarDollarHash_emptyTP, TXLbracketedDescription_anyTP, TXLpattern_anyTP);

    // Link the constructed match part into the rule's parse tree
    assert (stringcmp (*ident_idents[tree_trees[tree_kid5TP (ruleTP)].name], "TXL_optReplaceOrMatchPart_") == 0);
    assert (tree_trees[tree_kid1TP (tree_kid5TP (ruleTP))].name == empty_T);
    tree_setKidTree (tree_trees[tree_kid5TP (ruleTP)].kidsKP, TXLreplaceOrMatchPart_anyTP);
}

static void ruleCompiler_processReplacementAnonymous (tokenT targetT, treePT optByPartTP, rulePartsBaseT partIndex, struct ruleLocalsT *localVars)
{
    // create a new anonymous local construct as a parse of [empty],
    // replace the original anonymous in the replacement
    // with the new anonymous local
    
    // create the actual anonymous construct of the target type 
    ruleCompiler_makeAnonymousConstruct (targetT, partIndex, localVars);

    // make a reference for the new local and replace the anonymous
    // with it in the real construct
    const treePT anonTP = tree_newTreeInit (treeKind_id, rule_ruleParts[partIndex].name, rule_ruleParts[partIndex].name, 0, nilKid);

    // replace the anonymous in the real construct with the new local
    const treePT anonymousExpressionTP = txltree_optByPart_anonymousExpressionTP (optByPartTP);

    assert (tree_trees[tree_kid1TP (anonymousExpressionTP)].name == anonymous_T);
    tree_setKidTree (tree_trees[anonymousExpressionTP].kidsKP, anonTP);
}

static void ruleCompiler_enterRuleFormals (int ruleIndex, treePT arg_formalsTP)
{
    treePT formalsTP = arg_formalsTP;

    struct ruleT *r = &(rule_rules[ruleIndex]);

    if (r->called) {
        // rule has been previously called; back-check the parameter types

        // we need to copy the predicted formals to the new localsBase
        const int formalBase = r->localVars.localsBase;
        rule_setLocalsBase (ruleIndex, rule_ruleLocalCount);

        if (rule_ruleLocalCount + (r->localVars.nformals) > maxTotalRuleLocals) {
            string message;
            stringprintf (message, "Too many total local variables in rules of TXL program (> %d)", maxTotalRuleLocals);
            error (ruleCompiler_context, message, LIMIT_FATAL, 334);
        }

        for (int formalNum = 1; formalNum <= r->localVars.nformals; formalNum++) {
            if (tree_plural_emptyP (formalsTP)) {
                error (ruleCompiler_context, "Number of formal parameters does not agree with previous call", FATAL, 331);
            }

            // make the copy
            rule_cloneLocalVar (r->localVars.localsBase + formalNum, formalBase + formalNum);

            const struct ruleLocalT *formal = &(rule_ruleLocals[r->localVars.localsBase + formalNum]);
            rule_setLocalName (r->localVars.localsBase + formalNum, txltree_formal_nameT (tree_plural_firstTP (formalsTP)));

            const tokenT declaredFormalType = txltree_formal_typeT (tree_plural_firstTP (formalsTP));

            // Check that the declared target production has been defined
            symbol_findSymbol (declaredFormalType);

            if (formal->typename_ != declaredFormalType) {
                string message;
                stringprintf (message, "Type of formal parameter '%s' does not agree with previous call", 
                    *ident_idents[formal->name]);
                error (ruleCompiler_context, message, FATAL, 332);
            }

            // we start each formal with one reference to account for its
            // probable use in the calling scope
            rule_setLocalRefs (r->localVars.localsBase + formalNum, 1);
            rule_setLocalChanged (r->localVars.localsBase + formalNum, false);

            formalsTP = tree_plural_restTP (formalsTP);
        }

        // check number of parameters
        if (!tree_plural_emptyP (formalsTP)) {
            error (ruleCompiler_context, "Number of formal parameters does not agree with previous call", FATAL, 331);
        }

        rule_setNPreLocals (ruleIndex, r->localVars.nformals);
        rule_setNLocals (ruleIndex, r->localVars.nformals);

        // already checked room above
        rule_incLocalCount (r->localVars.nformals);

    } else {
        // rule has not been called yet - nothing to check against
        int formalNum = 0;
        rule_setLocalsBase (ruleIndex, rule_ruleLocalCount);

        if (rule_ruleLocalCount + maxParameters > maxTotalRuleLocals) {
            string message;
            stringprintf (message, "Too many total local variables in rules of TXL program (> %d)", maxTotalRuleLocals);
            error (ruleCompiler_context, message, LIMIT_FATAL, 334);
        }

        while (true) {
            if (tree_plural_emptyP (formalsTP)) break;

            if (formalNum == maxParameters) {
                string message;
                stringprintf (message, "Too many rule/function parameters (> %d)", maxParameters);
                error (ruleCompiler_context, message, LIMIT_FATAL, 311);
            }

            formalNum += 1;

            const int formalIndex = r->localVars.localsBase + formalNum;
            rule_setLocalName (formalIndex, txltree_formal_nameT (tree_plural_firstTP (formalsTP)));
            rule_setLocalType (formalIndex, txltree_formal_typeT (tree_plural_firstTP (formalsTP)));

            // Check that the paramter's nonterminal type has been defined
            symbol_findSymbol (rule_ruleLocals[formalIndex].typename_);

            // we start each formal with one reference to account for its
            // probable use in the calling scope
            rule_setLocalRefs (formalIndex, 1);
            rule_setLocalChanged (formalIndex, false);

            formalsTP = tree_plural_restTP (formalsTP);
        }

        rule_setNFormals (ruleIndex, formalNum);
        rule_setNPreLocals (ruleIndex, formalNum);
        rule_setNLocals (ruleIndex, formalNum);

        // already checked room above
        rule_incLocalCount (r->localVars.nformals);
    }
}

static treePT ruleCompiler_findLastRef (tokenT name, treePT replacementTP)
{
    // Used to find the last variable reference in a postpattern export in optimizeGlobalVariables ()
    // If it's a recursive export, and it is not referred to in the replacement (or following postexports), 
    // then we may be able to optimize it

    treePT lastrefTP = nilTree;

    if (replacementTP == nilTree) {
        return (nilTree);
    }

    treePT treeTP = replacementTP;

    // subtrees still to be searched
    #define maxSearchDepth 100
    struct searchStackEntry {
        kidPT kidsKP, endKP;
    };
    // 1-origin [1 .. maxSearchDepth]
    struct searchStackEntry searchStack[maxSearchDepth + 1];
    int searchTop = 0;

    while (true) {
        if ((tree_trees[treeTP].kind == treeKind_expression) && (tree_trees[treeTP].name == name)) {
            lastrefTP = treeTP;
        }

        if (tree_trees[treeTP].kind >= firstLeafKind) {
            // A terminal - 
            // pop any completed sequences ...
            while (true) {
                if (searchTop == 0) {
                    return (lastrefTP);
                }
                if (searchStack[searchTop].kidsKP < searchStack[searchTop].endKP) 
                    break;
                searchTop -= 1;
            }
            // ... and move on to the next subtree in the sequence
            searchStack[searchTop].kidsKP += 1;
            treeTP = tree_kids[searchStack[searchTop].kidsKP];

        } else if (tree_trees[treeTP].kind == treeKind_choose) {
            // One child - just go down to it (no need to come back)
            treeTP = tree_kids[tree_trees[treeTP].kidsKP];

        } else {
            // Push a new sequence of subtrees to check
            assert ((tree_trees[treeTP].kind == treeKind_order) 
                || (tree_trees[treeTP].kind == treeKind_repeat) 
                || (tree_trees[treeTP].kind == treeKind_list));

            if (searchTop >= maxSearchDepth) {
                return (nilTree);  // too complex, can't find it
            }

            searchTop += 1;
            searchStack[searchTop].kidsKP = tree_trees[treeTP].kidsKP;
            searchStack[searchTop].endKP = searchStack[searchTop].kidsKP + tree_trees[treeTP].count - 1;
            treeTP = tree_kids[tree_trees[treeTP].kidsKP];
        }
    }
    return (lastrefTP);
}

static void ruleCompiler_enterRuleBody (int ruleIndex, treePT ruleTP)
{
    // Save context in case we exit early
    string rulecontext;
    stringcpy (rulecontext, ruleCompiler_context);

    // Is it a rule, or a function?
    string ruleorfunction;
    substring (ruleorfunction, ruleCompiler_context, 1, stringindex (ruleCompiler_context, " '") - 1);

    // TXL 11.1, optional match/replace part 
    if (tree_plural_emptyP (txltree_rule_optReplaceOrMatchPartTP (ruleTP))) {
        // add default target [any]
        rule_setTarget (ruleIndex, any_T);
    } else {
        // enter target name and kind
        rule_setTarget (ruleIndex, txltree_rule_targetT (ruleTP));
    }

    struct ruleT *r = &(rule_rules[ruleIndex]);
    const int targetIndex = symbol_findSymbol (r->target);

    // keep track of calls from this rule
    rule_setCallsBase (ruleIndex, rule_ruleCallCount);
    rule_setNCalls (ruleIndex, 0);

    // process prePattern
    rule_setPrePatternPartsBase (ruleIndex, rule_rulePartCount);
    int prePatternCount = 0;
    treePT prePatternTP = txltree_rule_prePatternTP (ruleTP);

    while (true) {
        stringcpy (ruleCompiler_context, rulecontext);  // in case we exit

        if (tree_plural_emptyP (prePatternTP)) break;

        if (prePatternCount + 1 >= maxParts) {  // (sic)
            error (ruleCompiler_context, "Rule/function is too complex - simplify using subrules", LIMIT_FATAL, 335);
        }

        if (rule_rulePartCount + prePatternCount + 1 >= maxTotalRuleParts) {
            string message;
            stringprintf (message, "Too many total constructs, deconstructs and conditions in TXL program (> %d)", maxTotalRuleParts);
            error (ruleCompiler_context, message, LIMIT_FATAL, 337);
        }

        prePatternCount += 1;

        const treePT partTP = tree_kid1TP (tree_kid1TP (tree_kid1TP (prePatternTP)));
        string partName;
        stringcpy (partName, *ident_idents[tree_trees[partTP].name]);

        if (stringcmp (partName, "TXL_conditionPart_") == 0) {
            if (txltree_condition_isAnonymous (partTP)) {
                // add a construct for the empty anonymous
                ruleCompiler_processConditionAnonymous (txltree_rule_nameT (ruleTP), partTP, r->prePattern.partsBase + prePatternCount, 
                    &(r->localVars));
                prePatternCount += 1;  // checked above (see "sic")
                // now process the condition that uses it
            }

            ruleCompiler_processCondition (txltree_rule_nameT (ruleTP), partTP, r->prePattern.partsBase + prePatternCount, &(r->localVars));

        } else if (stringcmp (partName, "TXL_constructPart_") == 0) {
            if (txltree_construct_isAnonymous (partTP)) {
                // add a construct for the empty anonymous
                ruleCompiler_processConstructAnonymous (txltree_rule_nameT (ruleTP), partTP, r->prePattern.partsBase + prePatternCount, 
                    &(r->localVars));
                prePatternCount += 1;  // checked above (see "sic")
                // now process the construct that uses it
            }

            ruleCompiler_processConstruct (txltree_rule_nameT (ruleTP), partTP, r->prePattern.partsBase + prePatternCount, &(r->localVars));

            if (r->kind != ruleKind_function) {
                // we start each pre-construct with one reference to account for its
                // probable use in subsequent iterations of the rule
                rule_setLocalRefs (r->localVars.localsBase + rule_ruleParts[r->prePattern.partsBase + prePatternCount].nameRef, 1);
            }

        } else if (stringcmp (partName, "TXL_importPart_") == 0) {

            ruleCompiler_processImport (txltree_rule_nameT (ruleTP), partTP, r->prePattern.partsBase + prePatternCount, &(r->localVars));

        } else if (stringcmp (partName, "TXL_exportPart_") == 0) {
            if (txltree_construct_isAnonymous (partTP)) {
                // add a construct for the empty anonymous
                ruleCompiler_processConstructAnonymous (txltree_rule_nameT (ruleTP), partTP, r->prePattern.partsBase + prePatternCount, 
                    &(r->localVars));
                prePatternCount += 1;  // checked above (see "sic")
                // now process the construct that uses it
            }

            ruleCompiler_processExport (txltree_rule_nameT (ruleTP), partTP, r->prePattern.partsBase + prePatternCount, &(r->localVars));

        } else {
            assert (stringcmp (partName, "TXL_deconstructPart_") == 0);
            ruleCompiler_processDeconstruct (txltree_rule_nameT (ruleTP), partTP, r->prePattern.partsBase + prePatternCount, 
                &(r->localVars));
        }

        prePatternTP = tree_plural_restTP (prePatternTP);
    }

    rule_setNPreLocals (ruleIndex, r->localVars.nlocals);
    rule_setPrePatternNParts (ruleIndex, prePatternCount);

    // already checked above
    rule_incPartCount (prePatternCount);

    // TXL 11.1, optional match/replace part 
    if (tree_plural_emptyP (txltree_rule_optReplaceOrMatchPartTP (ruleTP))) {
        // add defalt match [any]
        ruleCompiler_makeDefaultMatchPart (ruleTP);
    }

    // process skipping
    const treePT optSkippingTP = txltree_rule_optSkippingTP (ruleTP);

    rule_setSkipName (ruleIndex, NOT_FOUND);
    rule_setSkipName (ruleIndex, NOT_FOUND);
    rule_setSkipName (ruleIndex, NOT_FOUND);

    if (! tree_plural_emptyP (optSkippingTP)) {
        tokenT skippingNameT = txltree_optSkippingNameT (optSkippingTP, 1) ;
        rule_setSkipName (ruleIndex, skippingNameT);
        // Check that the skipped production has been defined
        symbol_findSymbol (r->skipName);

        // Is there a second one?
        skippingNameT = txltree_optSkippingNameT (optSkippingTP, 2);

        if (skippingNameT != NOT_FOUND) {
            rule_setSkipName (ruleIndex, skippingNameT);
            // Check that the skipped production has been defined
            symbol_findSymbol (r->skipName);

            // How about a third one?
            skippingNameT = txltree_optSkippingNameT (optSkippingTP, 3);

            if (skippingNameT != NOT_FOUND) {
                rule_setSkipName (ruleIndex, skippingNameT);
                // Check that the skipped production has been defined
                symbol_findSymbol (r->skipName);
            }

        } else {
            // Check for optimizable case
            if (r->skipName == r->target) {
                // skipping [X] match/replace * [X]
                // potentially optimizable if all scopes are [repeat/list X]
                rule_setSkipRepeat (ruleIndex, true);
            } else {
                rule_setSkipRepeat (ruleIndex, false);
            }
        }
    }

    // process pattern
    stringprintf (ruleCompiler_context, "pattern of %s '%s'", ruleorfunction, *ident_idents[txltree_rule_nameT (ruleTP)]);

    treePT resultTP;
    ruleCompiler_processPatternOrReplacement (txltree_rule_targetT (ruleTP), txltree_rule_patternTP (ruleTP), &resultTP, &(r->localVars));
    rule_setPattern (ruleIndex, resultTP);

    rule_setStarred (ruleIndex, txltree_rule_isStarred (ruleTP));

    // process postpattern
    rule_setPostPatternPartsBase (ruleIndex, rule_rulePartCount);

    int postPatternCount = 0;
    bool hasPostConstruct = false;
    treePT postPatternTP = txltree_rule_postPatternTP (ruleTP);

    while(true) {
        stringcpy (ruleCompiler_context, rulecontext);  // in case we exit

        if (tree_plural_emptyP (postPatternTP)) break;

        if (postPatternCount + 1 >= maxParts) {  // (sic)
            error (ruleCompiler_context, "Rule/function is too complex - simplify using subrules", LIMIT_FATAL, 335);
        }

        if (rule_rulePartCount + postPatternCount + 1 >= maxTotalRuleParts) {
            string message;
            stringprintf (message, "Too many total constructs, deconstructs and conditions in TXL program (> %d)", maxTotalRuleParts);
            error (ruleCompiler_context, message, LIMIT_FATAL, 337);
        }

        postPatternCount += 1;

        const treePT partTP = tree_kid1TP (tree_kid1TP (tree_kid1TP (postPatternTP)));
        string partName;
        stringcpy (partName, *ident_idents[tree_trees[partTP].name]);

        if (stringcmp (partName, "TXL_conditionPart_") == 0) {
            // If we've already done a post construct, it may be discarded when this condition fails.
            // We correct for this possibility by marking each main pattern variable (or descendant thereof) 
            // that has been changed in a post construct as having an extra reference.  
            // This accounts for the possibility that its original value will be needed 
            // in the calling scope if/when this post condition fails.
            if (hasPostConstruct) {
                for (int i = r->localVars.nformals + 1; i <= r->localVars.nlocals; i++) {
                    if ((rule_ruleLocals[r->localVars.localsBase + i].changed) 
                            && (rule_ruleLocals[r->localVars.localsBase + i].refs == 1)) {
                        rule_incLocalRefs (r->localVars.localsBase + i, 1);
                    }
                }
            }

            if (txltree_condition_isAnonymous (partTP)) {
                // add a construct for the empty anonymous
                ruleCompiler_processConditionAnonymous (txltree_rule_nameT (ruleTP), partTP, r->postPattern.partsBase + postPatternCount,
                    &(r->localVars));
                postPatternCount += 1;  // checked above (see "sic")
                // now process the condition that uses it
            }

            ruleCompiler_processCondition (txltree_rule_nameT (ruleTP), partTP, r->postPattern.partsBase + postPatternCount,
                &(r->localVars));

        } else if (stringcmp (partName, "TXL_constructPart_") == 0) {
            hasPostConstruct = true;

            if (txltree_construct_isAnonymous (partTP)) {
                // add a construct for the empty anonymous
                ruleCompiler_processConstructAnonymous (txltree_rule_nameT (ruleTP), partTP, r->postPattern.partsBase + postPatternCount,
                    &(r->localVars));
                postPatternCount += 1;  // checked above (see "sic")
                // now process the construct that uses it
            }

            ruleCompiler_processConstruct (txltree_rule_nameT (ruleTP), partTP, r->postPattern.partsBase + postPatternCount,
                &(r->localVars));

        } else if (stringcmp (partName, "TXL_importPart_") == 0) {

            ruleCompiler_processImport (txltree_rule_nameT (ruleTP), partTP, r->postPattern.partsBase + postPatternCount, &(r->localVars));

        } else if (stringcmp (partName, "TXL_exportPart_") == 0) {
            if (txltree_construct_isAnonymous (partTP)) {
                // add a construct for the empty anonymous
                ruleCompiler_processConstructAnonymous (txltree_rule_nameT (ruleTP), partTP, r->postPattern.partsBase + postPatternCount,
                    &(r->localVars));
                postPatternCount += 1;  // checked above (see "sic")
                // now process the export that uses it
            }

            ruleCompiler_processExport (txltree_rule_nameT (ruleTP), partTP, r->postPattern.partsBase + postPatternCount, &(r->localVars));

        } else {
            assert (stringcmp (partName, "TXL_deconstructPart_") == 0);

            // If we've already done a post construct, it may be discarded when this condition fails.
            // We correct for this possibility by marking each main pattern variable (or descendant thereof) 
            // that has been changed in a post construct as having an extra reference.  
            // This accounts for the possibility that its original value will be needed 
            // in the calling scope if/when this post condition fails.
            if (hasPostConstruct) {
                for (int i = (r->localVars.nformals) + 1; i <= r->localVars.nlocals; i++) {
                    if ((rule_ruleLocals[r->localVars.localsBase + i].changed) 
                            && (rule_ruleLocals[r->localVars.localsBase + i].refs == 1)) {
                        rule_incLocalRefs (r->localVars.localsBase + i, 1);
                    }
                }
            }

            ruleCompiler_processDeconstruct (txltree_rule_nameT (ruleTP), partTP, r->postPattern.partsBase + postPatternCount,
                &(r->localVars));
        }

        postPatternTP = tree_plural_restTP (postPatternTP);
    }

    rule_setPostPatternNParts (ruleIndex, postPatternCount);

    // already checked room above
    rule_incPartCount (postPatternCount);

    // process replacement
    const treePT optByPartTP = txltree_rule_optByPartTP (ruleTP);

    if (txltree_rule_replaceOrMatchT (ruleTP) == replace_T) {

        if (tree_plural_emptyP (optByPartTP)) {
            error (ruleCompiler_context, "'replace' rule/function must have a replacement", FATAL, 338);

        } else {
            stringprintf (ruleCompiler_context, "replacement of %s '%s'", ruleorfunction, 
                *ident_idents[txltree_rule_nameT (ruleTP)]);

            if (txltree_optByPart_isAnonymous (optByPartTP)) {
                // add a construct for the empty anonymous
                hasPostConstruct = 1;

                if (postPatternCount >= maxParts) {
                    error (ruleCompiler_context, "Rule/function is too complex - simplify using subrules", LIMIT_FATAL, 335);
                }

                if (rule_rulePartCount + postPatternCount >= maxTotalRuleParts) {
                    string message;
                    stringprintf (message, "Too many total constructs, deconstructs and conditions in TXL program (> %d)", maxTotalRuleParts);
                    error (ruleCompiler_context, message, LIMIT_FATAL, 337);
                }

                postPatternCount += 1;
                rule_incPartCount (1);
                rule_setPostPatternNParts (ruleIndex, postPatternCount);

                ruleCompiler_processReplacementAnonymous (txltree_rule_targetT (ruleTP), optByPartTP, 
                    r->postPattern.partsBase + postPatternCount, &(r->localVars));
            }

            // can only optimize last references if they are in the replacement
            for (int i = r->localVars.nformals + 1; i <= r->localVars.nlocals; i++) {
                rule_setLocalLastRef (r->localVars.localsBase + i, 0);
            }

            ruleCompiler_processPatternOrReplacement (txltree_rule_targetT (ruleTP), txltree_optByPart_replacementTP (optByPartTP), 
                &resultTP, &(r->localVars));
            rule_setReplacement (ruleIndex, resultTP);

            // mark the last reference of each main- or post-pattern variable as optimizable
            // pre-pattern variables are not optimizable!
            for (int i = (r->localVars.nformals) + 1; i <= r->localVars.nlocals; i++) {
                if ((rule_ruleLocals[r->localVars.localsBase + i].lastref != nilTree) 
                        && (tree_trees[rule_ruleLocals[r->localVars.localsBase + i].lastref].kind == treeKind_expression) 
                        && (rule_ruleLocals[r->localVars.localsBase + i].basetypename != key_T) 
                        && (rule_ruleLocals[r->localVars.localsBase + i].basetypename != token_T)) {

                    // we must be careful that the variable was not *deconstructed* from
                    // a pre-pattern variable!
                    int reali = i;
                    while (true) {
                        if (rule_ruleLocals[r->localVars.localsBase + reali].partof == 0) break;
                        reali = rule_ruleLocals[r->localVars.localsBase + reali].partof;
                    }

                    if ((reali > r->localVars.nprelocals) 
                            // and that it is not a global variable or deconstructed from one!
                            && (!(rule_ruleLocals[r->localVars.localsBase + i].global)) 
                            && (!(rule_ruleLocals[r->localVars.localsBase + reali].global))) {
                        tree_setKind (rule_ruleLocals[r->localVars.localsBase + i].lastref, treeKind_lastExpression);
                    }
                }
            }
        }

    } else {
        assert (txltree_rule_replaceOrMatchT (ruleTP) == match_T);

        if (!tree_plural_emptyP (optByPartTP)) {
            error (ruleCompiler_context, "'match' rule/function cannot have a replacement", FATAL, 339);
        }

        rule_setReplacement (ruleIndex, nilTree);

        // If the match rule has a post construct, it may change a pattern variable - but match rules are not permitted to change anything. 
        // We correct for this possibility by marking each main pattern variable (or descendant thereof) 
        // that has been changed in a post construct as having an extra reference.  
        // This accounts for the possibility that its original value will be needed 
        // in the calling scope if the condition calling this match rule succeeds.
        if (hasPostConstruct) {
            for (int i = (r->localVars.nformals) + 1; i <= r->localVars.nlocals; i++) {
                if ((rule_ruleLocals[r->localVars.localsBase + i].changed) 
                        && (rule_ruleLocals[r->localVars.localsBase + i].refs == 1)) {
                    rule_incLocalRefs ((r->localVars.localsBase + i), 1);
                }
            }
        }
    }

    // synchronize the reference counts of children of deconstructed variables
    for (int i = (r->localVars.nformals) + 1; i <= r->localVars.nlocals; i++) {
        int parentvar = rule_ruleLocals[r->localVars.localsBase + i].partof;
        if (parentvar != 0) {
            rule_incLocalRefs (r->localVars.localsBase + i, (rule_ruleLocals[r->localVars.localsBase + parentvar].refs) - 1);

            // if the deconstructed parent is referenced in the replacement,
            // we cannot safely optimize the last reference to the child
            if (rule_ruleLocals[r->localVars.localsBase + parentvar].lastref != nilTree) {
                if ((rule_ruleLocals[r->localVars.localsBase + i].lastref != nilTree) 
                        && (tree_trees[rule_ruleLocals[r->localVars.localsBase + i].lastref].kind == treeKind_lastExpression)) {
                    tree_setKind (rule_ruleLocals[r->localVars.localsBase + i].lastref, treeKind_expression);
                }
            }

            // if the child is referenced in the replacement,
            // we cannot safely optimize the last reference to the deconstructed parent
            if (rule_ruleLocals[r->localVars.localsBase + i].lastref != nilTree) {
                if ((rule_ruleLocals[r->localVars.localsBase + parentvar].lastref != nilTree) 
                        && (tree_trees[rule_ruleLocals[r->localVars.localsBase + parentvar].lastref].kind == treeKind_lastExpression)) {
                    tree_setKind (rule_ruleLocals[r->localVars.localsBase + parentvar].lastref, treeKind_expression);
                }
            }
        }
    }

    // fix the reference counts of local variables of special types [key] and [token] - JRC 10.6.99
    for (int i = r->localVars.nformals + 1; i <= r->localVars.nlocals; i++) {
        if ((rule_ruleLocals[r->localVars.localsBase + i].basetypename == key_T) 
                || (rule_ruleLocals[r->localVars.localsBase + i].basetypename == token_T)) {
            rule_setLocalRefs (r->localVars.localsBase + i, 9);
        }
    }

    stringcpy (ruleCompiler_context, rulecontext);
}

static void ruleCompiler_checkUserDefinedRuleName (tokenT name)
{
    string *ruleName = (string *) (ident_idents[name]);
    if ((stringncmp (*ruleName, "list_", 5) == 0) 
            || (stringncmp (*ruleName, "repeat_", 7) == 0) 
            || (stringncmp (*ruleName, "opt_", 4) == 0) 
            || (stringncmp (*ruleName, "attr_", 5) == 0) 
            || (stringncmp (*ruleName, "lit_", 4) == 0) 
            || (stringncmp (*ruleName, "push_", 5) == 0) 
            || (stringncmp (*ruleName, "pop_", 4) == 0) 
            || (stringncmp (*ruleName, "TXL_", 4) == 0)) {
        error (ruleCompiler_context, "'list_', 'repeat_', 'opt_', 'attr_', 'lit_', 'push_', 'pop_' and 'TXL_' name prefixes are reserved for TXL internal use", FATAL, 340);
    }
}

static void ruleCompiler_processRule (treePT ruleTP)
{
    const tokenT ruleNameT = txltree_rule_nameT (ruleTP);
    stringprintf (ruleCompiler_context, "rule '%s'", *ident_idents[ruleNameT]);
    ruleCompiler_checkUserDefinedRuleName (ruleNameT);

    const int ruleIndex = rule_enterRule (ruleNameT);
    ruleCompiler_currentRuleIndex = ruleIndex;

    struct ruleT *r = &(rule_rules[ruleIndex]);

    if (r->defined) {
        if (ruleIndex <= nPredefinedRules) {
            error (ruleCompiler_context, "Rule/function declaration overrides predefined function", WARNING, 341);
        } else {
            error (ruleCompiler_context, "Rule/function has been previously defined", FATAL, 342);
        }
    }

    rule_setDefined (ruleIndex, true);
    rule_setKind (ruleIndex, ruleKind_rule);

    if (!(r->called)) {
        // TXL 11.1, optional match/replace part 
        if (tree_plural_emptyP (txltree_rule_optReplaceOrMatchPartTP (ruleTP))) {
            rule_setIsCondition (ruleIndex, true);
        } else {
            rule_setIsCondition (ruleIndex, (txltree_rule_replaceOrMatchT (ruleTP) == match_T));
        }
    }

    ruleCompiler_enterRuleFormals (ruleIndex, txltree_rule_formalsTP (ruleTP));
    ruleCompiler_enterRuleBody (ruleIndex, ruleTP);

    if ((r->called) && (r->isCondition) && (r->replacementTP != nilTree)) {
        error (ruleCompiler_context, "'replace' rule/function has been previously used as a 'where' condition", FATAL, 343);
    } else {
        rule_setIsCondition (ruleIndex, (r->replacementTP == nilTree));

        if (r->isCondition) {
            // optimize by treating it as a deep function
            rule_setStarred (ruleIndex, true);
            rule_setKind (ruleIndex, ruleKind_function);
        }
    }

    if (txltree_rule_isDollared (ruleTP) 
            && ((!(r->isCondition)) || (r->postPattern.nparts != 0))) {
        rule_setKind (ruleIndex, ruleKind_onepass);
    }

    if (((r->target == any_T) && (r->postPattern.nparts != 0)) && (!(r->isCondition))) {
        ruleCompiler_polymorphicProgram = true;
        if (options_option[verbose_p]) {
            error (ruleCompiler_context, "'replace' rule/function has target type [any] (results may not be well-formed)", WARNING, 344);
        }
    }
}

static void ruleCompiler_processFunction (const treePT ruleTP)
{
    const tokenT ruleNameT = txltree_rule_nameT (ruleTP);
    stringprintf (ruleCompiler_context, "function '%s'", *ident_idents[ruleNameT]);
    ruleCompiler_checkUserDefinedRuleName (ruleNameT);

    const int ruleIndex = rule_enterRule (ruleNameT);
    ruleCompiler_currentRuleIndex = ruleIndex;

    struct ruleT *r = &(rule_rules[ruleIndex]);

    if (r->defined) {
        if (ruleIndex <= nPredefinedRules) {
            error (ruleCompiler_context, "Rule/function declaration overrides predefined function", WARNING, 341);
        } else {
            error (ruleCompiler_context, "Rule/function has been previously defined", FATAL, 342);
        }
    }

    rule_setDefined (ruleIndex, true);
    rule_setKind (ruleIndex, ruleKind_function);

    if (!(r->called)) {
        // TXL 11.1, optional match/replace part 
        if (tree_plural_emptyP (txltree_rule_optReplaceOrMatchPartTP (ruleTP))) {
            rule_setIsCondition (ruleIndex, true);
        } else {
            rule_setIsCondition (ruleIndex, (txltree_rule_replaceOrMatchT (ruleTP) == match_T));
        }
    }

    ruleCompiler_enterRuleFormals (ruleIndex, txltree_rule_formalsTP (ruleTP));

    const tokenT callscopetype = r->target;
    const bool previouslyCalled = r->called;

    ruleCompiler_enterRuleBody (ruleIndex, ruleTP);

    if ((r->called) && (r->isCondition) && ((r->replacementTP) != nilTree)) {
        error (ruleCompiler_context, "'replace' rule/function has been previously used as a 'where' condition", FATAL, 343);
    } else {
        rule_setIsCondition (ruleIndex, (r->replacementTP == nilTree));
    }

    if (previouslyCalled && ((r->target) != callscopetype) && ((r->target) != any_T) && (callscopetype != any_T) && (!(r->starred))) {
        error (ruleCompiler_context, "Target type of function does not match scope of previous calls", WARNING, 348);
    }

    if ((options_option[verbose_p]) && (r->target == any_T) && (r->postPattern.nparts != 0) && (!(r->isCondition))) {
        error (ruleCompiler_context, "'replace' rule/function has target type [any] (results may not be well-formed)", WARNING, 344);
    }
}

static void ruleCompiler_processUndefinedRules (bool *undefinedRules)
{
    // Check that all called rules are defined.  If there are any 
    // query rule calls [?R], create a copy of the rule table entry
    // for [R] for the query rule.
 
    *undefinedRules = false;

    // We use a loop rather than a for loop in case a match rule
    // with an undefined base rule adds the undefined rule to the
    // rule table (see below)

    int r = nPredefinedRules + 1;

    while (true) {
        if (r > rule_nRules) break;

        if (!(rule_rules[r].defined)) {
            // First check to see if it is a query rule

            if (stringchar (*ident_idents[rule_rules[r].name], 1) == '?') {
                // A query rule - link it to the real rule, but as a match rule.
                // If the real rule is not defined, we will catch that
                // later in this same checking loop!

                string realRuleNameString;
                substring (realRuleNameString, *ident_idents[rule_rules[r].name], 2, stringlen (*ident_idents[rule_rules[r].name]));
                const tokenT realRuleName = ident_install (realRuleNameString, treeKind_id);

                // If the base rule is undefined, this may add an entry for it to the rule table!
                // We catch that in a later iteration of this same loop.
                const int realRuleIndex = rule_enterRule (realRuleName);

                // ? on predefined rules is undefined
                if (realRuleIndex <= nPredefinedRules) {
                    string message;
                    stringprintf (message, "[?] is not defined on predefined function [%s]", *ident_idents[rule_rules[realRuleIndex].name]);
                    error ("", message, DEFERRED, 352);
                    *undefinedRules = true;
                }

                rule_cloneRule (r, realRuleIndex);
                rule_setReplacement (r, nilTree);
                rule_setIsCondition (r, true);

                if (rule_rules[r].defined) {

                    if ((rule_rules[r].kind == ruleKind_rule) || (rule_rules[r].kind == ruleKind_onepass)) {
                        // optimize the new match rule by treating it as a deep function
                        rule_setStarred (r, true);
                        rule_setKind (r, ruleKind_function);
                    }

                    // If the new match rule has a post construct, it may change a pattern variable - 
                    // but match rules are not permitted to change anything. 
                    // We correct for this possibility by marking each main pattern variable (or descendant thereof) 
                    // that has been changed in a post construct as having an extra reference.  
                    // This accounts for the possibility that its original value will be needed 
                    // in the calling scope if the condition calling this match rule succeeds.
                    bool hasPostConstruct = false;

                    for (int p = 1; p <= rule_rules[r].postPattern.nparts; p++) {
                        if (rule_ruleParts[rule_rules[r].postPattern.partsBase + p].kind == rulePart_construct) {
                            hasPostConstruct = true;
                        }
                    }

                    if (hasPostConstruct) {
                        for (int i = (rule_rules[r].localVars.nformals) + 1; i <= rule_rules[r].localVars.nlocals; i++) {
                            if ((rule_ruleLocals[rule_rules[r].localVars.localsBase + i].changed) 
                                    && (rule_ruleLocals[rule_rules[r].localVars.localsBase + i].refs == 1)) {
                                rule_incLocalRefs ((rule_rules[r].localVars.localsBase + i), 1);
                            }
                        }
                    }
                }

            } else {
                string message;
                stringprintf (message, "Rule/function '%s' has not been defined", *ident_idents[rule_rules[r].name]);
                error ("", message, DEFERRED, 353);
                *undefinedRules = true;
            }
        }

        r += 1;
    }
}

static void ruleCompiler_processGlobalVariables (bool *globalErrors)
{
    // Find all the global variables imported or exported from rules
    // and enter them in the global scope.  Check global variable type consistency.

    *globalErrors = 0;

    // set up predefined globals
    const tokenT repeat_stringlit_T = ident_install ("repeat_0_stringlit", treeKind_id);

    // identify global environment
    const tokenT globalEnvironmentName = ident_install ("global", treeKind_id);
    rule_rules[globalR].name = globalEnvironmentName;

    // standard predefined globals
    rule_setLocalsBase (globalR, rule_ruleLocalCount);
    struct ruleLocalsT *globalVars = &(rule_rules[globalR].localVars);

    int pdindex;
    pdindex = rule_enterLocalVar ("", globalVars, TXLargs_T, repeat_stringlit_T);
    assert (pdindex == TXLargsG);
    pdindex = rule_enterLocalVar ("", globalVars, TXLprogram_T, stringlit_T);
    assert (pdindex == TXLprogramG);
    pdindex = rule_enterLocalVar ("", globalVars, TXLinput_T, stringlit_T);
    assert (pdindex == TXLinputG);
    pdindex = rule_enterLocalVar ("", globalVars, TXLexitcode_T, number_T);
    assert (pdindex == TXLexitcodeG);

    assert (pdindex == numGlobalVars);
    assert (rule_rules[globalR].localVars.nlocals == numGlobalVars);

    for (int ir = nPredefinedRules + 1; ir <= rule_nRules; ir++) {
        struct ruleT *r = &(rule_rules[ir]);
        struct ruleT *globals = &(rule_rules[globalR]);

        for (int p = 1; p <= r->prePattern.nparts; p++) {
            const int partIndex = r->prePattern.partsBase + p;
            struct rulePartT *part = &(rule_ruleParts[partIndex]);

            if ((part->kind == rulePart_import) || (part->kind == rulePart_export)) {
                const int globalVarRef = rule_lookupLocalVar ("", &(globals->localVars), (part->name));

                if (globalVarRef == 0) {
                    string context;
                    stringprintf (context, "rule/function '%s'", *ident_idents[r->name]);
                    const int globalIndex = rule_enterLocalVar (context, &(globals->localVars), part->name, part->target);
                    rule_setPartGlobalRef (partIndex, globalIndex);

                } else if (rule_ruleParts[partIndex].target != rule_ruleLocals[globals->localVars.localsBase + globalVarRef].typename_) {
                    string context, message;
                    stringprintf (context, "rule/function '%s'", *ident_idents[r->name]);
                    stringprintf (message, "Type of imported/exported variable '%s' does not match global variable", 
                        *ident_idents[rule_ruleParts[partIndex].name]);
                    error (context, message, DEFERRED, 354);
                    *globalErrors = true;

                } else {
                    rule_setPartGlobalRef (partIndex, globalVarRef);
                }
            }
        }

        for (int p = 1; p <= r->postPattern.nparts; p++) {
            const int partIndex = r->postPattern.partsBase + p;
            struct rulePartT *part = &(rule_ruleParts[partIndex]);

            if ((part->kind == rulePart_import) || (part->kind == rulePart_export)) {
                const int globalVarRef = rule_lookupLocalVar ("", &(globals->localVars), (part->name));

                if (globalVarRef == 0) {
                    string context;
                    stringprintf (context, "rule/function '%s'", *ident_idents[r->name]);
                    const int globalIndex = rule_enterLocalVar (context, &(globals->localVars), part->name, part->target);
                    rule_setPartGlobalRef (partIndex, globalIndex);

                } else if (rule_ruleParts[partIndex].target != rule_ruleLocals[globals->localVars.localsBase + globalVarRef].typename_) {
                    string context, message;
                    stringprintf (context, "rule/function '%s'", *ident_idents[r->name]);
                    stringprintf (message, "Type of imported/exported variable '%s' does not match global variable", 
                        *ident_idents[rule_ruleParts[partIndex].name]);
                    error (context, message, DEFERRED, 354);
                    *globalErrors = true;

                } else {
                    rule_setPartGlobalRef (partIndex, globalVarRef);
                }
            }
        }
    }
}

// Reachability, for rule analysis - 1-origin [1 .. maxSymbols]
static array (treePT, ruleCompiler_reachList);
static int ruleCompiler_reachLength;  // 0

static bool ruleCompiler_real_reachable (const treePT defineTP, const treePT targetTP, const int depth)
{
    // reachable (X,Y) = true if X is of type Y,
    //            = true if X is of type choose, and reachable (one kid of X,Y)
    //            = true if X is of type order, and reachable (one kid of X,Y)

    if (depth > symbol_nSymbols) {
        // give up, don't know, probably no
        return (false);
    }

    // Is this the one we're looking for?
    if ((tree_trees[defineTP].name == tree_trees[targetTP].name) && (tree_trees[defineTP].kind == tree_trees[targetTP].kind)) {
        return (true);
    }

    // If not, is it worth looking deeper?
    if (tree_trees[defineTP].kind >= firstLeafKind) {
        return ((tree_trees[defineTP].kind == treeKind_token) && (tree_trees[targetTP].kind >= firstLiteralKind));
    }

    // Keep track of where we've already looked
    if (depth == 0) {
        ruleCompiler_reachLength = 0;
    }

    for (int i = 1; i <= ruleCompiler_reachLength; i++) {
        if ((tree_trees[ruleCompiler_reachList[i]].name == tree_trees[defineTP].name) 
                && (tree_trees[ruleCompiler_reachList[i]].kind == tree_trees[defineTP].kind)) {
            // been there, done that
            return (false);
        }
    }

    assert (ruleCompiler_reachLength < symbol_nSymbols);
    ruleCompiler_reachLength += 1;
    ruleCompiler_reachList[ruleCompiler_reachLength] = defineTP;

    // Now look deeper
    if ((tree_trees[defineTP].kind == treeKind_generaterepeat) || (tree_trees[defineTP].kind == treeKind_generatelist)) {
        return ((tree_trees[targetTP].kind == treeKind_empty) || ruleCompiler_real_reachable (tree_kid1TP (defineTP), targetTP, depth + 1));
    } else if (tree_trees[defineTP].kind == treeKind_lookahead) {
        return (tree_trees[targetTP].kind == treeKind_empty);
    } else if ((tree_trees[defineTP].kind == treeKind_choose) || (tree_trees[defineTP].kind == treeKind_leftchoose) 
            || (tree_trees[defineTP].kind == treeKind_order)) {
        for (int i = 1; i <= tree_trees[defineTP].count; i++) {
            if (ruleCompiler_real_reachable (tree_kidTP (i, defineTP), targetTP, depth + 1)) {
                return (true);
            }
        }
        return (false);
    } else if ((tree_trees[defineTP].kind == treeKind_repeat) || (tree_trees[defineTP].kind == treeKind_list)) {
        assert (tree_trees[defineTP].count == 2);
        return (ruleCompiler_real_reachable (tree_kid2TP (defineTP), targetTP, depth + 1) 
             || ruleCompiler_real_reachable (tree_kid1TP (defineTP), targetTP, depth + 1));
    } else {
        return (false);
    }
}

// Reachability cache for speed
#define reachableCacheSize 30
struct ruleCompiler_reachableCacheEntry {
    treePT defineTP, targetTP;
    bool yes;
};
static struct ruleCompiler_reachableCacheEntry ruleCompiler_reachableCache[reachableCacheSize];

static int ruleCompiler_reachableCacheTop;  // 0

static bool ruleCompiler_reachable (const treePT defineTP, const treePT targetTP)
{
    for (int i = 1; i <= ruleCompiler_reachableCacheTop; i++) {
        if ((ruleCompiler_reachableCache[i - 1].targetTP == targetTP) && (ruleCompiler_reachableCache[i - 1].defineTP == defineTP)) {
            return (ruleCompiler_reachableCache[i - 1].yes);
        }
    }

    if (ruleCompiler_reachableCacheTop < reachableCacheSize) {
        ruleCompiler_reachableCacheTop += 1;
        struct ruleCompiler_reachableCacheEntry *rc = &(ruleCompiler_reachableCache[ruleCompiler_reachableCacheTop - 1]);
        rc->defineTP = defineTP;
        rc->targetTP = targetTP;
        rc->yes = ruleCompiler_real_reachable (defineTP, targetTP, 0);
        return (rc->yes);
    } else {
        return (ruleCompiler_real_reachable (defineTP, targetTP, 0));
    }
}

static bool ruleCompiler_possiblyEmpty (const struct ruleT *r, const treePT replacementTP, const int depth)
{
    // possiblyEmpty (X) = true if X is of type empty, generaterepeat or generatelist,
    //              = true if X is of type choose, and possiblyEmpty (kid of X)
    //              = true if X is of type order, repeat or list, and possiblyEmpty (all kids of X)

    if (depth > symbol_nSymbols) {
        // give up, don't know, probably yes
        return (true);
    }

    if ((tree_trees[replacementTP].kind == treeKind_empty) 
            || (tree_trees[replacementTP].kind == treeKind_generaterepeat) 
            || (tree_trees[replacementTP].kind == treeKind_generatelist)
            || (tree_trees[replacementTP].kind == treeKind_lookahead)) {
        return (true);

    } else if ((tree_trees[replacementTP].kind == treeKind_choose) 
            || (tree_trees[replacementTP].kind == treeKind_leftchoose)) {
        return (ruleCompiler_possiblyEmpty (r, tree_kid1TP (replacementTP), depth + 1));

    } else if ((tree_trees[replacementTP].kind == treeKind_order) 
            || (tree_trees[replacementTP].kind == treeKind_repeat) 
            || (tree_trees[replacementTP].kind == treeKind_list)) {
        for (int i = 1; i <= tree_trees[replacementTP].count; i++) {
            if (!ruleCompiler_possiblyEmpty (r, tree_kidTP (i, replacementTP), depth + 1)) {
                return (false);
            }
        }
        return (true);

    } else if ((tree_trees[replacementTP].kind == treeKind_expression) || (tree_trees[replacementTP].kind == treeKind_lastExpression)) {
        const int localIndex = tree_trees[replacementTP].count;
        const int symbolIndex = symbol_findSymbol ((rule_ruleLocals[r->localVars.localsBase + localIndex].typename_));
        return (ruleCompiler_possiblyEmpty (r, symbol_symbols[symbolIndex], depth + 1));

    } else {
        return (false);
    }
}

static void ruleCompiler_unreachable_target_warning (const tokenT ruleName, const tokenT calledRuleName, const tokenT localName, const tokenT localTypeName)
{
    string context, message;
    stringprintf (context, "rule/function '%s'", *ident_idents[ruleName]);
    string extlocalTypeName;
    externalType (*ident_idents[localTypeName], extlocalTypeName);
    stringprintf (message, "Scope '%s [%s]' of call to rule/function '%s' can never contain a match", 
        *ident_idents[localName], extlocalTypeName, *ident_idents[calledRuleName]);
    error (context, message, WARNING, 356);
}

static void ruleCompiler_empty_result_warning (const tokenT ruleName, const tokenT calledRuleName, const tokenT localName, const tokenT localTypeName, const tokenT repeat1TypeName)
{
    string context, message;
    string extrepeat1TypeName;
    externalType (*ident_idents[repeat1TypeName], extrepeat1TypeName);
    string extlocalTypeName;
    externalType (*ident_idents[localTypeName], extlocalTypeName);
    stringprintf (context, "rule/function '%s'", *ident_idents[ruleName]);
    stringprintf (message, "Call to rule/function '%s' with scope '%s [%s]' may yield an empty result for embedded [%s]",
        *ident_idents[calledRuleName], *ident_idents[localName],
        extlocalTypeName, extrepeat1TypeName);
    error (context, message, WARNING, 357);
}

static void ruleCompiler_checkRuleCallScopes (const treePT replacementTP, const struct ruleT *r, bool *scopeErrors) 
{
    // Find every rule call in the replacement tree and check that its scope type
    // is reasonable

    if (replacementTP == nilTree) {
        return;
    }

    switch (tree_trees[replacementTP].kind) {

        case treeKind_order: case treeKind_repeat: case treeKind_list:
            {
                kidPT replacementKidsKP = tree_trees[replacementTP].kidsKP;
                const kidPT endKP = replacementKidsKP + (tree_trees[replacementTP].count);
                assert (replacementKidsKP != nilKid);
                while (true) {
                    ruleCompiler_checkRuleCallScopes (tree_kids[replacementKidsKP], r, scopeErrors);
                    replacementKidsKP += 1;
                    if (replacementKidsKP >= endKP) break;
                }
            }
            break;

        case treeKind_choose:
            {
                const kidPT replacementKidKP = tree_trees[replacementTP].kidsKP;
                ruleCompiler_checkRuleCallScopes (tree_kids[replacementKidKP], r, scopeErrors);
            }
            break;

        case treeKind_literal: case treeKind_stringlit: case treeKind_charlit: case treeKind_number: case treeKind_id: case treeKind_comment:
        case treeKind_usertoken1: case treeKind_usertoken2: case treeKind_usertoken3: case treeKind_usertoken4: case treeKind_usertoken5:
        case treeKind_usertoken6: case treeKind_usertoken7: case treeKind_usertoken8: case treeKind_usertoken9: case treeKind_usertoken10:
        case treeKind_usertoken11: case treeKind_usertoken12: case treeKind_usertoken13: case treeKind_usertoken14: case treeKind_usertoken15:
        case treeKind_usertoken16: case treeKind_usertoken17: case treeKind_usertoken18: case treeKind_usertoken19: case treeKind_usertoken20:
        case treeKind_usertoken21: case treeKind_usertoken22: case treeKind_usertoken23: case treeKind_usertoken24: case treeKind_usertoken25:
        case treeKind_usertoken26: case treeKind_usertoken27: case treeKind_usertoken28: case treeKind_usertoken29: case treeKind_usertoken30:
        case treeKind_empty: case treeKind_token: case treeKind_key: case treeKind_upperlowerid: case treeKind_upperid: case treeKind_lowerupperid:
        case treeKind_lowerid: case treeKind_floatnumber: case treeKind_decimalnumber: case treeKind_integernumber: case treeKind_newline:
        case treeKind_space: case treeKind_srclinenumber: case treeKind_srcfilename:
            {
                return;
            }
            break;

        case treeKind_expression: case treeKind_lastExpression:
            {
                const int localIndex = tree_trees[replacementTP].count;
                const int scopeSymbolIndex = symbol_findSymbol ((rule_ruleLocals[r->localVars.localsBase + localIndex].typename_));
                const treePT scopeTypeTP = symbol_symbols[scopeSymbolIndex];

                kidPT ruleCallsKP = tree_trees[replacementTP].kidsKP;

                if ((ruleCallsKP != nilKid) 
                        && (stringncmp (*ident_idents[rule_ruleLocals[r->localVars.localsBase + localIndex].name], 
                            "_anonymous_", 11) != 0)) {

                    // Process each rule called, and check target is reachable from the scope
                    while (true) {
                        assert (tree_trees[tree_kids[ruleCallsKP]].kind == treeKind_ruleCall);

                        // called rule index is encoded in the name field of the call!
                        const int calledRuleIndex = tree_trees[tree_kids[ruleCallsKP]].name;

                        if (calledRuleIndex > nPredefinedRules) {
                            // Check scope for anomalies
                            const int targetIndex = symbol_findSymbol ((rule_rules[calledRuleIndex].target));
                            const treePT targetTypeTP = symbol_symbols[targetIndex];

                            // First check: can we ever match, with this scope?
                            treePT targetType0TP = targetTypeTP;
                            if ((stringncmp (*ident_idents[rule_rules[calledRuleIndex].target], "repeat_1_", 9) == 0) 
                                    || (stringncmp (*ident_idents[rule_rules[calledRuleIndex].target], "list_1_", 7) == 0)) {
                                targetType0TP = symbol_symbols[targetIndex - 1];
                            }

                            if ((tree_trees[targetType0TP].name != any_T) 
                                    && (tree_trees[scopeTypeTP].name != any_T) 
                                    && (tree_trees[targetType0TP].name != key_T) 
                                    && (!ruleCompiler_reachable (scopeTypeTP, targetType0TP))) {
                                if (!ruleCompiler_polymorphicProgram) {
                                    ruleCompiler_unreachable_target_warning (r->name, rule_rules[calledRuleIndex].name, 
                                        rule_ruleLocals[r->localVars.localsBase + localIndex].name, 
                                        rule_ruleLocals[r->localVars.localsBase + localIndex].typename_);
                                }
                            }

                            // Second check: can we ever make an empty [repeat] in a scope containing [repeat+] ?
                            if (options_option[analyze_p]) {
                                if (((stringncmp (*ident_idents[rule_rules[calledRuleIndex].target], "repeat_0_", 9) == 0) 
                                        || (stringncmp (*ident_idents[rule_rules[calledRuleIndex].target], "list_0_", 7) == 0))
                                    && (((rule_rules[calledRuleIndex].kind == ruleKind_rule) 
                                        || (rule_rules[calledRuleIndex].kind == ruleKind_onepass) 
                                        || ((rule_rules[calledRuleIndex].kind == ruleKind_function) 
                                                && (rule_rules[calledRuleIndex].starred)))) 
                                    && (rule_rules[calledRuleIndex].replacementTP != nilTree) 
                                    && ruleCompiler_possiblyEmpty (&(rule_rules[calledRuleIndex]), rule_rules[calledRuleIndex].replacementTP, 0)) {
                                    // The corresponding [repeat_1_X] or [list_1_X] follows the original in the symbol table
                                    const treePT targetType1TP = symbol_symbols[targetIndex + 1];
                                    if (ruleCompiler_reachable (scopeTypeTP, targetType1TP)) {
                                        ruleCompiler_empty_result_warning (r->name, rule_rules[calledRuleIndex].name, 
                                            rule_ruleLocals[r->localVars.localsBase + localIndex].name, 
                                            rule_ruleLocals[r->localVars.localsBase + localIndex].typename_, 
                                            tree_trees[targetType1TP].name);
                                    }
                                }
                            }

                            // Third check: is an optimizable skipping [X] ever called with a scope that is not [repeat X] for the skipped [X]?
                            if (rule_rules[calledRuleIndex].skipRepeat) {
                                if (tree_isListOrRepeatType (tree_trees[scopeTypeTP].name) && (tree_trees[targetTypeTP].name == 
                                        tree_listOrRepeatBaseType (tree_trees[scopeTypeTP].name))) {
                                    // skipping [X] match/replace * [X] in [repeat/list X]
                                } else {
                                    // this call can't be optimized, so we give up on the optimization
                                    rule_setSkipRepeat (calledRuleIndex, false);
                                }
                            }
                        }

                        ruleCallsKP += 1;
                        if (tree_kids[ruleCallsKP] == 0) break;
                    }
                }
            }
            break;

        default :
            {
                error ("", "Fatal TXL error in checkRuleCallScopes", INTERNAL_FATAL, 359);
            }
            break;
    }
}

static void ruleCompiler_processRuleCalls (bool *scopeErrors)
{
    // Find all rule calls and check that their targets are reachable from their scopes.

    *scopeErrors = false;

    for (int r = nPredefinedRules + 1; r <= rule_nRules; r++) {
        ruleCompiler_checkRuleCallScopes (rule_rules[r].replacementTP, &(rule_rules[r]), scopeErrors);

        for (int p = 1; p <= rule_rules[r].prePattern.nparts; p++) {
            struct rulePartT *part = &(rule_ruleParts[rule_rules[r].prePattern.partsBase + p]);
            if ((part->kind == rulePart_construct) || (part->kind == rulePart_export) 
                    || (part->kind == rulePart_cond) || (part->kind == rulePart_assert)) {
                ruleCompiler_checkRuleCallScopes (part->replacementTP, &(rule_rules[r]), scopeErrors);
            }
        }

        for (int p = 1; p <= rule_rules[r].postPattern.nparts; p++) {
            struct rulePartT *part = &(rule_ruleParts[rule_rules[r].postPattern.partsBase + p]);
            if ((part->kind == rulePart_construct) || (part->kind == rulePart_export) 
                    || (part->kind == rulePart_cond) || (part->kind == rulePart_assert)) {
                ruleCompiler_checkRuleCallScopes (part->replacementTP, &(rule_rules[r]), scopeErrors);
            }
        }
    }

    // Skipping main rule target is never optimizable 
    rule_setSkipRepeat (mainRule, false);
}

static bool ruleCompiler_callsRule (const int ruleIndex, const treePT replacementTP)
{
    // Does this replacement call the given rule?
    if (replacementTP == nilTree) {
        return (false);
    }

    switch (tree_trees[replacementTP].kind) {
        case treeKind_order: case treeKind_repeat: case treeKind_list:
            {
                kidPT replacementKidsKP = tree_trees[replacementTP].kidsKP;
                const kidPT endKP = replacementKidsKP + (tree_trees[replacementTP].count);
                bool kidsCallRule = false;
                while (true) {
                    kidsCallRule = kidsCallRule || ruleCompiler_callsRule (ruleIndex, (tree_kids[replacementKidsKP]));
                    replacementKidsKP += 1;
                    if (replacementKidsKP >= endKP) break;
                }
                return (kidsCallRule);
            }
            break;

        case treeKind_choose:
            {
                const kidPT replacementKidKP = tree_trees[replacementTP].kidsKP;
                return (ruleCompiler_callsRule (ruleIndex, (tree_kids[replacementKidKP])));
            }
            break;

        case treeKind_literal: case treeKind_stringlit: case treeKind_charlit: case treeKind_number: case treeKind_id: case treeKind_comment:
        case treeKind_usertoken1: case treeKind_usertoken2: case treeKind_usertoken3: case treeKind_usertoken4: case treeKind_usertoken5:
        case treeKind_usertoken6: case treeKind_usertoken7: case treeKind_usertoken8: case treeKind_usertoken9: case treeKind_usertoken10:
        case treeKind_usertoken11: case treeKind_usertoken12: case treeKind_usertoken13: case treeKind_usertoken14: case treeKind_usertoken15:
        case treeKind_usertoken16: case treeKind_usertoken17: case treeKind_usertoken18: case treeKind_usertoken19: case treeKind_usertoken20:
        case treeKind_usertoken21: case treeKind_usertoken22: case treeKind_usertoken23: case treeKind_usertoken24: case treeKind_usertoken25:
        case treeKind_usertoken26: case treeKind_usertoken27: case treeKind_usertoken28: case treeKind_usertoken29: case treeKind_usertoken30:
        case treeKind_empty: case treeKind_token: case treeKind_key: case treeKind_upperlowerid: case treeKind_upperid: case treeKind_lowerupperid:
        case treeKind_lowerid: case treeKind_floatnumber: case treeKind_decimalnumber: case treeKind_integernumber: case treeKind_newline:
        case treeKind_space: case treeKind_srclinenumber: case treeKind_srcfilename:
            {
                return (false);
            }
            break;

        case treeKind_expression: case treeKind_lastExpression:
            {
                // the count field tells us the ruleLocals index
                kidPT ruleCallsKP = tree_trees[replacementTP].kidsKP;

                if (ruleCallsKP != nilKid) {
                    // Process each rule called, and check target is reachable from the scope
                    while (true) {
                        assert (tree_trees[tree_kids[ruleCallsKP]].kind == treeKind_ruleCall);

                        // rule index encoded in the name field of the call
                        if (tree_trees[tree_kids[ruleCallsKP]].name == ruleIndex) {
                            return (true);
                        }

                        ruleCallsKP += 1;
                        if (tree_kids[ruleCallsKP] == nilTree) break;
                    }
                }

                return (false);
            }
            break;

        default :
            {
                error ("", "Fatal TXL error in callsRule", INTERNAL_FATAL, 360);
                return (false);
            }
            break;
    }
}

// Check whether called rules import a global before the call - 1-origin [1 .. maxRules]
static array (int, ruleCompiler_callerIndex);
static int ruleCompiler_callerDepth;  // 0

static bool ruleCompiler_callersPreImportGlobal (const int ruleIndex, const tokenT globalName)
{
    // Do any rules called by this rule pre-import the given global?

    if (ruleCompiler_callerDepth == rule_nRules) {
        return (false);  // give up, don't know, probably not
    }

    for (int c = 1; c <= ruleCompiler_callerDepth; c++) {
        // if we're in a recursive loop, then no
        if (ruleCompiler_callerIndex[c] == ruleIndex) {
            return (false);
        }
    }

    // process the next level of calls
    ruleCompiler_callerDepth += 1;
    ruleCompiler_callerIndex[ruleCompiler_callerDepth] = ruleIndex;

    for (int rindex = nPredefinedRules + 1; rindex <= rule_nRules; rindex++) {
        // for each rule in the rule table
        const struct ruleT *r = &(rule_rules[rindex]);

        for (int c = 1; c <= r->calledRules.ncalls; c++) {

            // if it calls this rule
            if (rule_ruleCalls[r->calledRules.callsBase + c] == ruleIndex) {

                // and it uses the given global
                const int localIndex = rule_lookupLocalVar (ruleCompiler_context, &(r->localVars), globalName);
                if ((localIndex != NOT_FOUND) && (rule_ruleLocals[r->localVars.localsBase + localIndex].global)) {

                    // does it import it in the pre-pattern before it calls the rule?
                    for (int p = 1; p <= r->prePattern.nparts; p++) {

                        // for each pre-pattern import
                        if ((rule_ruleParts[r->prePattern.partsBase + p].kind == rulePart_import)
                                && (rule_ruleParts[r->prePattern.partsBase + p].name == globalName)) {

                            // does it call the rule in the pre-pattern after the import?
                            for (int pp = p + 1; pp <= r->prePattern.nparts; pp++) {
                                if (rule_ruleParts[r->prePattern.partsBase + pp].name == globalName) break;

                                if (((rule_ruleParts[r->prePattern.partsBase + pp].kind == rulePart_construct) 
                                        || (rule_ruleParts[r->prePattern.partsBase + pp].kind == rulePart_export)) 
                                            && ruleCompiler_callsRule (ruleIndex, 
                                                rule_ruleParts[r->prePattern.partsBase + pp].replacementTP)) {
                                    ruleCompiler_callerDepth -= 1;
                                    return (true);
                                }
                            }

                            // or does it call it in the post-pattern?
                            for (int pp = 1; pp <= r->postPattern.nparts; pp++) {
                                if (rule_ruleParts[r->postPattern.partsBase + pp].name == globalName) break;

                                if (((rule_ruleParts[r->postPattern.partsBase + pp].kind == rulePart_construct) 
                                        || (rule_ruleParts[r->postPattern.partsBase + pp].kind == rulePart_export)) 
                                            && ruleCompiler_callsRule (ruleIndex, 
                                                rule_ruleParts[r->postPattern.partsBase + pp].replacementTP)) {
                                    ruleCompiler_callerDepth -= 1;
                                    return (true);
                                }
                            }
                        }
                    }


                    // does it import it in the post-pattern before it calls the rule?
                    for (int p = 1; p <= r->postPattern.nparts; p++) {

                        // for each post-pattern import
                        if ((rule_ruleParts[r->postPattern.partsBase + p].kind == rulePart_import) 
                                && (rule_ruleParts[r->postPattern.partsBase + p].name == globalName)) {

                            // does it call the rule in the post-pattern after the import?
                            for (int pp = p + 1; pp <= r->postPattern.nparts; pp++) {
                                if (rule_ruleParts[r->postPattern.partsBase + pp].name == globalName) break;

                                if (((rule_ruleParts[r->postPattern.partsBase + pp].kind == rulePart_construct) 
                                        || (rule_ruleParts[r->postPattern.partsBase + pp].kind == rulePart_export)) 
                                            && ruleCompiler_callsRule (ruleIndex, 
                                                rule_ruleParts[r->postPattern.partsBase + pp].replacementTP)) {
                                    ruleCompiler_callerDepth -= 1;
                                    return (true);
                                }
                            }
                        }
                    }
                }

                if (ruleCompiler_callersPreImportGlobal (rindex, globalName)) {
                    ruleCompiler_callerDepth -= 1;
                    return (true);
                }
            }
        }
    }

    ruleCompiler_callerDepth -= 1;
    return (false);
}

static void ruleCompiler_optimizeGlobalVariables (void) 
{
    // Find all global variable tail-recursive updates
    // and optimize to avoid copying

    for (int rindex = nPredefinedRules + 1; rindex <= rule_nRules; rindex++) {
        // for each rule in the rule table
        const struct ruleT *r = &(rule_rules[rindex]);

        // If the last thing in the postpattern is a recursive export,
        // and it is not referred to in the replacement (or following postexports), 
        // then we can optimize it

        for (int i = r->postPattern.nparts; i >= 1; i--) {
            if (rule_ruleParts[r->postPattern.partsBase + i].kind != rulePart_export) break;

            // it's an export
            treePT lastRecursiveRefTP = nilTree;
            lastRecursiveRefTP = ruleCompiler_findLastRef (rule_ruleParts[r->postPattern.partsBase + i].name, 
                rule_ruleParts[r->postPattern.partsBase + i].replacementTP);

            // is it recursive?
            if (lastRecursiveRefTP != nilTree) {

                // is it referred to after exporting?
                treePT lastPostExportRefTP = nilTree;
                for (int j = i + 1; j <= r->postPattern.nparts; j++) {
                    lastPostExportRefTP = ruleCompiler_findLastRef (rule_ruleParts[r->postPattern.partsBase + i].name, 
                        rule_ruleParts[r->postPattern.partsBase + j].replacementTP);
                    if (lastPostExportRefTP != nilTree) break;
                }

                // or in the replacement?
                const treePT lastReplacementRefTP = ruleCompiler_findLastRef (rule_ruleParts[r->postPattern.partsBase + i].name, 
                    r->replacementTP);

                // if not, then it can be optimized without copying
                if (((lastPostExportRefTP == nilTree) && (lastReplacementRefTP == nilTree)) 
                        && (!ruleCompiler_callersPreImportGlobal (rindex, rule_ruleParts[r->postPattern.partsBase + i].name))) {
                    tree_setKind (lastRecursiveRefTP, treeKind_lastExpression);
                }
            }
        }
    }
}

void ruleCompiler_makeRuleTable (const treePT txlParseTreeTP)
{
    // predefined rules must be initialized
    assert (rule_nRules == nPredefinedRules);

    // now process all rule definitions
    treePT statementsLeftTP = txltree_program_statementsTP (txlParseTreeTP);
    ruleCompiler_polymorphicProgram = false;

    while (true) {
        if (tree_plural_emptyP (statementsLeftTP)) break;

        treePT statementTP = txltree_statement_keyDefRuleTP (tree_plural_firstTP (statementsLeftTP));
        string statementType;
        stringcpy (statementType, *ident_idents[tree_trees[statementTP].name]);

        if (stringcmp (statementType, "TXL_ruleStatement_") == 0) {
            ruleCompiler_processRule (statementTP);

        } else if (stringcmp (statementType, "TXL_functionStatement_") == 0) {
            ruleCompiler_processFunction (statementTP);

        } else {
            assert ((stringcmp (statementType, "TXL_keysStatement_") == 0) 
                || (stringcmp (statementType, "TXL_defineStatement_") == 0));
            // handled previously when creating the object language
            // grammar tree, so ignore now
        }

        statementsLeftTP = tree_plural_restTP (statementsLeftTP);
    }

    // check that all rules have been defined, and process query rule conversions
    bool undefinedRules = false;

    ruleCompiler_processUndefinedRules (&undefinedRules);

    if (undefinedRules) {
        throw (QUIT);
    }

    // identify the main rule
    const tokenT mainRuleName = ident_install ("main", treeKind_id);

    for (int mr = 1; mr <= rule_nRules; mr++) {
        if (rule_rules[mr].name == mainRuleName) {
            mainRule = mr;
            break;
        }
    }

    if (rule_nRules == nPredefinedRules) {
        error ("", "No rules/functions defined, assuming parse only", INFORMATION, 364);
        mainRule = rule_enterRule (mainRuleName);
        rule_setDefined (mainRule, false);
        return;

    } else if (mainRule == NOT_FOUND) {
            error ("", "Rule/function 'main' has not been defined", FATAL, 361);

    } else {
        const struct ruleT *main = &(rule_rules[mainRule]);
        if ((main->kind == ruleKind_function) && (!(main->starred))) {
            const tokenT programT = ident_lookup ("program");
            if ((main->target != programT) && (main->target != any_T)) {
                error ("", "Function 'main' can never match input type [program] (use a rule, searching function, or target type [program] instead)", FATAL, 362);
            }
        }
    }

    // Process global variable and check that import/export types are consistent
    bool globalErrors = false;

    ruleCompiler_processGlobalVariables (&globalErrors);

    if (globalErrors) {
        throw (QUIT);
    }

    // Check that rule call scope types are reasonable 
    if (options_option[analyze_p]) {
        error ("", "Analyzing the transformation rule set", INFORMATION, 363);
    }

    bool scopeErrors = false;

    ruleCompiler_processRuleCalls (&scopeErrors);

    if (scopeErrors) {
        throw (QUIT);
    }

    // Optimize global variable updates
    ruleCompiler_optimizeGlobalVariables ();

}

// Initialization
void ruleCompiler (void) {
    stringcpy (ruleCompiler_context, "");
    ruleCompiler_currentRuleIndex = 0;
    ruleCompiler_polymorphicProgram = false;
    ruleCompiler_lastWarningTokensTP = nilTree;

    // 1-origin [1 .. maxSymbols]
    arrayalloc (maxSymbols + 1, treePT, ruleCompiler_reachList);
    ruleCompiler_reachList[0] = UNUSED;
    ruleCompiler_reachLength = 0;
    ruleCompiler_reachableCacheTop = 0;

    // 1-origin [1 .. maxRules]
    arrayalloc (maxRules + 1, int, ruleCompiler_callerIndex);
    ruleCompiler_callerIndex[0] = UNUSED;
    ruleCompiler_callerDepth = 0;
}
